Connect nodes at same level - Java

Example

Input Tree
       A
      / \
     B   C
    / \   \
   D   E   F


Output Tree
       A---> NULL
      / \
     B--> C--> NULL
    / \   \
   D--> E--> F--> NULL

Method 1 (Extend Level Order Traversal or BFS)

Connect nodes at same level using constant extra space:

Tournament Tree (Winner Tree) and Binary Heap

Reference:

http://www.geeksforgeeks.org/tournament-tree-and-binary-heap/

Check if a given Binary Tree is SumTree - Java

Program:

Reference:
http://www.geeksforgeeks.org/check-if-a-given-binary-tree-is-sumtree/

Double Tree

Write a program that converts a given tree to its Double tree. To create Double tree of the given tree, create a new duplicate for each node, and insert the duplicate as the left child of the original node.
So the tree…

    2
   / \
  1   3

is changed to…

       2
      / \
     2   3
    /   /
   1   3
  /
 1

And the tree

            1
          /   \
        2      3
      /  \
    4     5

is changed to

               1
             /   \
           1      3
          /      /
        2       3
      /  \
     2    5
    /    /
   4   5
  /   
 4    

Program:

Reference:

http://www.geeksforgeeks.org/double-tree/

Root to leaf path sum equal to a given number

Idea:

- First check base conditions as per arguments passed in function.
- Take a subsum as a local variable for per stack which substracts the previous node values.
- check if node is leaf and subsum equals to zero then return true.
- if we find above condition true in any call then it has DONE and return true for each calls.


Program:

Inorder Tree Traversal without recursion and without stack in java

Using Morris Traversal, we can traverse the tree without using stack and recursion. The idea of Morris Traversal is based on Threaded Binary Tree. In this traversal, we first create links to Inorder successor and print the data using these links, and finally revert the changes to restore original tree.

Program :

Reference:
http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/

Convert an arbitrary Binary Tree to a tree that holds Children Sum Property

Question: Given an arbitrary binary tree, convert it to a binary tree that holds Children Sum Property. You can only increment data values in any node (You cannot change structure of tree and cannot decrement value of any node).

For example, the below tree doesn’t hold the children sum property, convert it to a tree that holds the property.

             50
           /     \     
         /         \
       7             2
     / \             /\
   /     \          /   \
  3        5      1      30

Now convert the root, we have to increment left subtree for converting the root.

          50
        /    \     
      /        \
    19           31
   / \           /  \
 /     \       /      \
14      5     1       30

Java Implementation:

static void convertMaxSumTree(Node root){
  
  if(root == null || (root.left == null && root.right == null)) return;
  
  int sum = 0 ;
  
  convertMaxSumTree(root.left);
  
  convertMaxSumTree(root.right);
  
  if(root.left != null){
   sum += root.left.data;
  }
  
  if(root.right != null)
   sum += root.right.data;
  
  int diff = sum - root.data;
  
  if(diff > 0){
   root.data += diff;
  }else if(diff < 0){
   increaseValue(root, -diff);
  }
  
  
 }
 
 private static void increaseValue(Node root, int diff) {

  //if(root == null) return;
  
  if(root.left != null)
  {
   root.left.data += diff;
   increaseValue(root.left, diff);
  }else if(root.right != null)
  {
   root.right.data += diff;
   increaseValue(root.right, diff);
  }
 }