[CC150] Chapter 4 Trees and Graphs
4.1 Implement a function to check if a binary tree is balanced. For the purpose of this question, a balanced tree is defined to be a tree such that the heights of the two subtrees of any node never differ by more than one.
This problem is in leetcode as Balanced Binary Tree.
4.2 Given a directed graph, design an algorithm to find out whether there is a route between two nodes.
Both BFS and DFS works. Here I use iterative BFS.
4.3 Given a sorted (increasing order) array, write an algorithm to create a binary search tree with minimal height.
This problem is in leetcode as Convert Sorted Array To Binary Search.
Related problem: Convert Sorted List To Binary Search.
4.4 Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (e.g., if you have a tree with depth D, you will have D linked lists).
This problem is equivalent to Binary Tree Level Order Traversal.
Related problem: Binary Tree Zigzag Level Order Traversal.
4.5 Implement a function to check if a binary tree is a binary search tree.
This problem is in leetcode as Validate Binary Search Tree.
4.6 Write an algorithm to find the "next" node (i.e., in-order successor) of a given node in a binary search tree. You may assume that each node has a link to its parent.
If the node has a right child: the "next" node is the leftmost leaf in the subtree of right child.
If the node does not have a right child: while the node is the right child of its parent, goes up until the node is the left child of its parent or the node is the root.
4.7 Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not necessary to be a binary search tree.
TBF.
4.8 You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide whether T2 is a subtree of T1. A tree T2 is a subtree of T1 if there exists a node n in T1 such that the subtree of n is identical to T2. That is, if you cut off the tree at node n, the two trees would be identical.
TBF.
4.9 You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum to a given value. Note that a path can start or end anywhere in the tree.
TBF.
This problem is in leetcode as Balanced Binary Tree.
4.2 Given a directed graph, design an algorithm to find out whether there is a route between two nodes.
Both BFS and DFS works. Here I use iterative BFS.
4.3 Given a sorted (increasing order) array, write an algorithm to create a binary search tree with minimal height.
This problem is in leetcode as Convert Sorted Array To Binary Search.
Related problem: Convert Sorted List To Binary Search.
4.4 Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (e.g., if you have a tree with depth D, you will have D linked lists).
This problem is equivalent to Binary Tree Level Order Traversal.
Related problem: Binary Tree Zigzag Level Order Traversal.
4.5 Implement a function to check if a binary tree is a binary search tree.
This problem is in leetcode as Validate Binary Search Tree.
4.6 Write an algorithm to find the "next" node (i.e., in-order successor) of a given node in a binary search tree. You may assume that each node has a link to its parent.
If the node has a right child: the "next" node is the leftmost leaf in the subtree of right child.
If the node does not have a right child: while the node is the right child of its parent, goes up until the node is the left child of its parent or the node is the root.
4.7 Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not necessary to be a binary search tree.
TBF.
4.8 You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide whether T2 is a subtree of T1. A tree T2 is a subtree of T1 if there exists a node n in T1 such that the subtree of n is identical to T2. That is, if you cut off the tree at node n, the two trees would be identical.
TBF.
4.9 You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum to a given value. Note that a path can start or end anywhere in the tree.
TBF.
Comments
Post a Comment