SDE - 1

We have discussed an efficient solution to find LCA in Binary Search Tree. In Binary Search Tree, using BST properties, we can find LCA in O(h) time where h is the height of the tree. Such an implementation is not possible in Binary Tree as keys Binary Tree nodes don’t follow any order. The following are different approaches to find LCA in Binary Tree.

Method 1: (By Storing root to n1 and root to n2 paths): 
Following is a simple O(n) algorithm to find LCA of n1 and n2. 
1) Find a path from the root to n1 and store it in a vector or array. 
2) Find a path from the root to n2 and store it in another vector or array. 
3) Traverse both paths till the values in arrays are the same. Return the common element just before the mismatch.

Time Complexity: The time complexity of the above solution is O(n). The tree is traversed twice, and then path arrays are compared. 

Method 2 (Using Single Traversal) 
Method 1 finds LCA in O(n) time but requires three tree traversals plus extra spaces for path arrays. If we assume that the keys n1 and n2 are present in Binary Tree, we can find LCA using a single traversal of Binary Tree and without extra storage for path arrays. 
The idea is to traverse the tree starting from the root. If any of the given keys (n1 and n2) matches with the root, then the root is LCA (assuming that both keys are present). If the root doesn’t match with any of the keys, we recur for the left and right subtree. The node which has one key present in its left subtree and the other key present in the right subtree is the LCA. If both keys lie in the left subtree, then the left subtree has LCA also, otherwise, LCA lies in the right subtree.

Time Complexity: The time complexity of the above solution is O(n) as the method does a simple tree traversal in a bottom-up fashion.

Inorder Traversal: 

Algorithm Inorder(tree)
1. Traverse the left subtree, i.e., call Inorder(left-subtree)
2. Visit the root.
3. Traverse the right subtree, i.e., call Inorder(right-subtree)
Uses of Inorder 
In the case of binary search trees (BST), Inorder traversal gives nodes in non-decreasing order. To get nodes of BST in non-increasing order, a variation of Inorder traversal where Inorder traversal s reversed can be used. 


Preorder Traversal: 

Algorithm Preorder(tree)
1. Visit the root.
2. Traverse the left subtree, i.e., call Preorder(left-subtree)
3. Traverse the right subtree, i.e., call Preorder(right-subtree) 
Uses of Preorder 
Preorder traversal is used to create a copy of the tree. Preorder traversal is also used to get prefix expression on an expression tree.

Postorder Traversal: 

Algorithm Postorder(tree)
1. Traverse the left subtree, i.e., call Postorder(left-subtree)
2. Traverse the right subtree, i.e., call Postorder(right-subtree)
3. Visit the root.