##### Tree questions patterns

Pattern relation to Binary search tree:

1. Check if a binary tree is BST

2. Construct BST from preorder traversal

3. Print postorder from preorder traversal of a BST

4. Inorder successor of a node in BST

There are some problems in which the fact that the binary tree is a BST makes the solution quicker. If we solve these with general binary tree approach these might take O(n^2) but using the property of BST it generally reduces to O(n) solution. The general pattern is to create a min and max bound for the nodes in the BST and keep narrowing that min max bound as we progress in the tree.

1. Here for the root will have a bound of Integer.MIN_VALUE and Integer.MAX_VALUE. If we traverse left in the BST the maximum value should be bound by the value of parent node. If we traverse right the minimum value should be bound by the value of parent node. If any node's value is out of these bounds then the binary tree is not a BST.

if(node == null) return true;

if(node.data <= min || node.data >= max) return false;

return IsBST(node.left, min, node.data) && IsBST(node.right, node.data, max)

2. A naive approach would take O(n^2) time. Preorder traversal gives the root. Since it is a BST the first node which is greater than the root marks the start of right subtree. All the nodes before that are part of left subtree. In the recursive solution we will need to search the first greater node than root and this searching takes O(n) time in O(n) recursive calls. Hence overall time O(n^2).

Better approach would be to again bound using min max.

if(preIndex == pre.length) return;

int key = preOrder[preIndex];

if(key > min && key < max) {

Node node = new Node(key);

preIndex++;

node.left = rec(pre, min, key);

node.right = rec(pre, key, max);

}

return node;

3. Follow the same approach as the above two. Just make sure you are printing after the two recursive calls (this will ensure postorder).

4. The general solution for inorder successor is a complex one with backtracking. The fact that the binary tree is BST, can simplify the solution for inorder successor. The inorder traversal of a BST gives ascending order. For a given node in BST it's inorder successor is the node which is the smallest node greater than the given node. The solution can be divided in two parts:

a. If the given node has a right child, then the inorder successor is the minimum node starting from the right child. Can be done with a simple loop.

b. If the given node has no right child, then we need to find the first parent for which this node is in the left subtree (this will give us the first greater element than the node).

while(root != null) {

if(node.data < root.data) {

succ = root;

root = root.left;

} else if(node.data > root.data)

root = root.right;

else break;

}

Construction from traversals:

1. Given preorder and inorder traversal construct the binary tree

1. The preorder traversal always gives the root. In inorder traversal the root is always in the middle. So if we search for the root from preorder traversal in the inorder traversal, the values to the left of root are part of the left subtree and values to the right are part of right subtree. By finding the index we can continuously narrow the inorder traversal to be searched.

if(inStart > inEnd) return null;

int val = pre[preIndex++];

int inIndex = search(in, inStart, inEnd, val);

Node node = new Node(val);

node.left = rec(pre, in, inStart, inIndex-1);

node.right = rec(pre, in, inIndex+1, inEnd);

Also while searching we have to search between inStart and inEnd and not the whole array.

Inorder successor:

1. Inorder successor of a node in Binary Tree

2. Populate inorder successor for all nodes in Binary tree

Inorder successor of a given node is the node that comes just after the given node in the inorder traversal of the tree. The inorder successor of the rightmost node in the tree is null.

1. The problem can be broken down in three parts:

a. If the right child of the node whose successor is to be found is not null, then the inorder successor is the leftmost node starting from the right child. This can be found with a simple while loop.

b. If the node itself is the rightmost node of the tree, then simply return null.

c. If the node does not have a right child, then we know that the inorder traversal will start going towards the parents of the node. Now, there are two possibilities of going towards parent node. Either you are a left child and going from the left side to parent or you are right child going from right side.

If we are going from the left side then the immediate parent is inorder successor (Why? because the order of inorder traversal is left root right). However, if we are going from right side then the inorder successor is one of the grandparents of the node (Why? The order is left root right. If we have processed the right, then we need to find the first parent node for which our right node is in the left subtree of the parent). This can be solved by backtracking. We keep returning the last visited node to the upper recursive call. If the last visited node is left child of the root node in the upper recursive call, then we have found the inorder successor.

if(root == null) return null;

if(root == targetNode) return targetNode;

Node temp = null;

temp = (temp = rec(node.left, targetNode)) != null ? temp : rec(node.right, targetNode);

if(temp != null && root.left == temp) {

//successor found

return null;

}

return root;

2. To populate the inorder successors for all nodes, we will do a reverse inorder traversal and keep track of the last node visited.