Binary Tree Algorithms

1) Find deepest node of a binary tree
(Karumanchi, pg 120)

2) Find height of a binary tree (recursion method)
(Karumanchi, pg 119 , with small correction)

3) Find height of binary tree (non recursion)
(Karumanchi, pg 120, with small correction)

4) Find Least Common Ancestor of 2 nodes in a binary tree
(Karumanchi, pg 126)
https://www.youtube.com/watch?v=13m9ZCB8gjw

5) Find Least Common Ancestor of 2 nodes in a binary SEARCH tree
(Karumanchi, pg 153)

6) Find Shortest path of 2 nodes in a binary SEARCH tree
(Hint: Find LCA and then calculate path from LCA to each node)

7) Determine if a Binary Tree is a Binary Search Tree
http://leetcode.com/2010/09/determine-if-binary-tree-is-binary.html
(Karumanchi : pg 155, prob 52)

8) Serialize and Deserialize a Binary Tree
http://www.geeksforgeeks.org/serialize-deserialize-binary-tree/
http://www.careercup.com/question?id=6228581160058880
http://leetcode.com/2010/09/serializationdeserialization-of-binary.html

8 b) Serialize and Deserialize a Binary Search Tree
https://www.youtube.com/watch?v=H594EV9OuDI
http://leetcode.com/2010/09/saving-binary-search-tree-to-file.html

9) Given a string of html tags like “< a >< b >< c >< /c >< d >< /d >< a >< /a >< /b >< /a >“, construct a tree where each node is like
Node { string tag, ArrayOfChildren[] };
Note that the tree need not be binary tree.
This was asked in SugarCRM.

 


BuildTree(root, parent) {
   tag = readTag(); // assume function readTag will output each tag serially 
   if (isOpenTag(tag)) {
       node = new Node;  // create a new Node
       node.tag = tag; 
       Stack.push(node); // push into stack 
       if (root == NULL) { 
           root = node;  
       } elseif (parent != NULL) {
           AddChild(parent, node);
           BuildTree(root, node);  // Build tree with node as parent 
       } else {
          // error
       }
   } else {
       temp = Stack.pop();
       if (Stack.NotEmpty()) { 
          parent = Stack.pop; 
          BuildTree(root, parent);  
       }
   }
   return root; 
}