Binary Search Tree: Any Path Sum

You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum up to that value. Note that it can be any path in the tree - it does not have to start at the root.

Input/Output:

printing inorder: 

1 3 4 5 6 7 8 9 10 12 13 15 17 

printing preorder: 

7 5 3 1 4 6 12 9 8 10 15 13 17 

printing path(s):

7 -> 5 -> null

5 -> 3 -> 4 -> null

12 -> null

Binary Tree: Is SubTree ?

You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.

Approach 1:
T1 has 10 million nodes—this means that the data alone is about 40 mb. We could create a string representing the inorder and preorder traversals. If T2’s preorder traversal is a substring of T1’s preorder traversal, and T2’s inorder traversal is a substring of T1’s inorder traversal, then T2 is a substring of T1. We can check this using a suffix tree. However, we may hit memory limitations because suffix trees are extremely memory intensive. If this become an issue, we can use an alternative approach.

Approach 2:
Find all the occurances of  T2's root node in T1 and then check recursively if the binary tree matches or not.

Binary Search Tree: Least Common Ancestor

Least common ancestor of 2 nodes in a binary search tree:

Approach:
The main idea of the solution is — While traversing Binary Search Tree from top to bottom, the first node n we encounter with value between n1 and n2, i.e., n1 < n < n2 is the Lowest or Least Common Ancestor(LCA) of n1 and n2 (where n1 < n2). 
So just traverse the BST in pre-order, if you find a node with value in between n1 and n2 then n is the LCA,
 if it's value is greater than both n1 and n2 then our LCA lies on left side of the node,
 if it's value is smaller than both n1 and n2 then LCA lies on right side.

Binary Tree: Least Common Ancestor

Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. NOTE: This is not necessarily a binary search tree.

Approach:
Do the inorder traversal and store it in an array I
Then do the preorder traversal and store it in an array P

Inorder: D B F G E A C
PreOrder: A B D E F G C


Suppose we need to find LCA for nodes D and F
mark the positions in inorder array and find first preorder ptr which seprates it into two
different parts of Inorder array

for above example first preorder ptr is "B" which seprates inorder into "D" and "F G E A C"
so "B" is first commom ancester of "D" and "F".

Binary Tree: Inorder Predecessor

Write an algorithm to find the ‘previous’ node (e.g., in-order predecessor) of a given node in a binary search tree where each node has a link to its parent.


To Find the inorder predecessor of node u:
If u has a left child, l, then pred(u) is the rightmost descendent of l
Otherwise, pred(u) is the closest ancestor, v, of u (if any) such that u is de-
scended from the right child of v.
If there is no such ancestor, then pred(u) is undefined.

The running time of TREE-SUCCESSOR on a tree of height his O(h), since we either follow a path up the tree or follow a path down the tree. The procedure TREE-PREDECESSOR, which is symmetric to TREE-SUCCESSOR, also runs in time O(h).

Taking the nodes one at a time and applying the rule:
node C: Does not have a left child. Closest ancestor such that node-C is de-
scended from the right child is node-A. Therefore, the predecessor of node-C
is node-A.
node A: Has a left child, node-B. Rightmost descendent of node-B is node-E.
node E: Has a left child, node-F. Rightmost descendent of node-F is node-G.
node G: Does not have a left child. Closest ancestor such that node-G is de-
scended from the right child is node-F.
node F: Does not have a left child. Closest ancestor such that node-F is de-
scended from the right child is node-B.
node B: Has a left child, node-D. Rightmost descendent of node-D is node-D
itself.
node D: Does not have a left child. There is no ancestor such that node-D is
descended from the right child. Therefore, the predecessor of node-D is
undefined.

BinaryTree: Inorder Successor

Write an algorithm to find the ‘next’ node (e.g., in-order successor) of a given node in a binary search tree where each node has a link to its parent.Inorder Successor

Approach:
To Find the inorder successor of node u:
If u has a right child, r, then succ(u) is the leftmost descendent of r

Otherwise, succ(u) is the closest ancestor, v, of u (if any) such that u is de-
scended from the left child of v. If there is no such ancestor, then succ(u) is
undefined.

The running time of TREE-SUCCESSOR on a tree of height his O(h), since we either follow a path up the tree or follow a path down the tree. The procedure TREE-PREDECESSOR, which is symmetric to TREE-SUCCESSOR, also runs in time O(h).

Taking the nodes one at a time and applying the rule:
node D: Does not have a right child. Its successor is the closest ancestor, v
such that node-D is descended from the left child of v. Node-D is descended
from the left child of node-B, so succ(D) is node-B.
node B: Has a right child (node-E), so successor is the leftmost descendent of
node-E, namely node-F.
node F: Has a right child (node-G), so successor is the leftmost descendent of
node-G, namely node-G itself.
node G: Does not have a right child. Its successor is the closest ancestor, v
such that node-G is descended from the left child of v. Node-G is descended
from the left child of node-E, so succ(G) is node-E.
node E: Does not have a right child. Its successor is the closest ancestor, v
such that node-E is descended from the left child of v. Node-E is descended
from the left child of node-A, so succ(E) is node-A.
node A: Has a right child (node-C), so successor is the leftmost descendent of
node-C, namely node-C itself.
node C: Does not have a right child. Its successor would be the closest ances-
tor, v such that node-C is descended from the left child of v. However,
there is no such ancestor, so succ(C) is undefined (node-C has no succes-
sor).

Code:

Binary Tree: level order linked list

Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (eg, if you have a tree with depth D, you’ll have D linked lists).

Approach:
We can do breadth first traversal of the tree keeping track of the levels, and create a linkedlist of all the nodes at any particular level

Input/Output:
iterative inorder:
3 7 9 15 17 21 25
printing level order:
15
7 21
3 9 17 25

Printing linked list at each level:
Level: 0
15
Level: 1
7 21
Level: 2
3 9 17 25

Binary Tree: Min Height

Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height.

Approach:
We need to create a binary tree such that the number of nodes in left subtree and right subtree are equal if possible.

1. Pick the mid element of the array as the root of the binary tree.
2. The left part of the subarray goes into the left subtree.
3. The right part of the subarray goes into the right subtree.
4. Recurse.

Graphs: find path between 2 nodes.

Given a directed graph, design an algorithm to find out whether there is a route between two nodes.

Approach:
This problem can be solved by just simple graph traversal, such as depth first search or breadth first search. We start with one of the two nodes and, during traversal, check if the other node is found. We should mark any node found in the course of the algorithm as ‘already visited’ to avoid cycles and repetition of the nodes.

Binary Tree: Is Balanced or not.

Implement a function to check if a tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that no two leaf nodes differ in distance from the root by more than one.

Approach:
The idea is: the difference of min depth and max depth should not exceed 1, since the difference of the min and the max depth is the maximum distance difference possible in the tree.

Input/Output:

Inorder:
3 7 9 15 17 19 21 25
is tree balanced: true
Inorder:
3 7 9 15 17 19 20 21 25
is tree balanced: false