Print
 

Binary Tree: Coding Problems

Binary Tree is a data struc­ture consisted of nodes con­tain­ing data and two ref­er­ences to other nodes, one on the left and one on the right.

Binary Tree con­sist of Nodes

class Node{
	int data; 
	Node left;
	Node right;	
	public Node(int data){
		this.data = data;
		left = null;
		right = null;
	}
       public setLeftNode(Node node){
		this.left = node;
	}
       public setRightNode(Node node){
		this.right = node;
	}  
}

Tree definitions:

Java Binary Tree Structure

public class BinaryTree { 
  private Node root;   // Root node pointer. Will be null for an empty tree. 
  
  private static class Node { 
    Node left; 
    Node right; 
    int data; 

    Node(int newData) { 
      left = null; 
      right = null; 
      data = newData; 
    } 
  } 
  // Create empty binary tree
  public void BinaryTree() { 
    root = null; 
  }
 
  public void insert(int data) { 
    root = insert(root, data); 
  } 
 private Node insert(Node node, int data) { 
    if (node==null) { 
      node = new Node(data); 
    } 
    else { 
      if (data <= node.data) { 
        node.left = insert(node.left, data); 
      } 
      else { 
        node.right = insert(node.right, data); 
      } 
    } 
    return(node); // in any case, return the new pointer to the caller 
  } 
}  

Oper­a­tions

Insert(int n) : Add a node with value n O(lgn)

Find(int n) : Find a node with value n O(lgn)

Delete (int n) : Delete a node with value n O(lgn)

Dis­play(): Prints the entire tree in increas­ing order O(n)

 

Classic Tree problems

Most of the solutions use two methods: a one-line OOP method that starts the computation, and a recursive method that does the real operation.

Size

Returns the number of nodes in the tree

public int size() { 
  return(size(root)); 
} 
private int size(Node node) { 
  if (node == null) return(0); 
  else { 
    return(size(node.left) + 1 + size(node.right)); 
  } 
} 

Max Depth

Returns the max root-to-leaf depth of the tree

public int maxDepth() { 
  return(maxDepth(root)); 
} 
private int maxDepth(Node node) { 
  if (node==null) { 
    return(0); 
  } 
  else { 
    int lDepth = maxDepth(node.left); 
    int rDepth = maxDepth(node.right); 
    return(Math.max(lDepth, rDepth) + 1); 
  } 
} 
  

Min value

Returns the min value in a non-empty binary search tree

public int minValue() { 
 return( minValue(root) ); 
} 

private int minValue(Node node) { 
  Node current = node; 
  while (current.left != null) { 
    current = current.left; 
  } 
  return(current.data); 
} 
  

Max value

Returns the max value in a non-empty binary search tree

public int maxValue() { 
 return( maxValue(root) ); 
} 

private int maxValue(Node node) { 
  Node current = node; 
  while (current.right != null) { 
    current = current.right; 
  } 
  return(current.data); 
} 
  

Inorder print of tree

Prints the node values in the "inorder" order

public void printInOrderTree() { 
 printInOrderTree(root); 
 System.out.println(); 
} 
private void printInOrderTree(Node node) { 
 if (node == null) return; 

 // left, node itself, right 
 printInOrderTree(node.left); 
 System.out.print(node.data + "  "); 
 printInOrderTree(node.right); 
} 

Postorderprint of tree

Prints the node values in the "postorder" order

public void printPostOrderTree() { 
 printPostOrderTree(root); 
 System.out.println(); 
} 
private void printPostOrderTree(Node node) { 
 if (node == null) return; 

 printPostOrderTree(node.left); 
 printPostOrderTree(node.right); 
 System.out.print(node.data + "  "); 
} 

PreOrder print of tree

Recursion

Prints the node values in the "preorder" order

public void printPreOrderTree() { 
 printPreOrderTree(root); 
 System.out.println(); 
} 
private void printPreOrderTree(Node node) { 
 if (node == null) return; 
 System.out.print(node.data + "  "); 
 printPreOrderTree(node.left); 
 printPreOrderTree(node.right); 

} 

Without recursion (Traversal)

public class Solution {
    public ArrayList<Integer> preorderTraversal(Node root) {
        ArrayList<Integer> returnList = new ArrayList<Integer>();
 
        if(root == null)
            return returnList;
 
        Stack stack = new Stack();
        stack.push(root);
 
        while(!stack.empty()){
            TreeNode n = stack.pop();
            returnList.add(n.val);
 
            if(n.right != null){
                stack.push(n.right);
            }
            if(n.left != null){
                stack.push(n.left);
            }
 
        }
        return returnList;
    }
   public void print(Node root){
          ArrayList<Integer> 
          list =  preorderTraversal(root);
          for(Integer item: list){
               System.out.println(item.data);	
         }  }
}

Print in Level order (Traversal)

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:

Given binary tree {3,9,20,#,#,15,7},

   
    4
   / \
  8  22
      /  \
   11   6

return its level order traversal as [[4], [8,22], [11,6]]

public ArrayList<ArrayList> levelOrder(TreeNode root) {
    ArrayList<ArrayList<Integer>> al = new ArrayList<ArrayList<Integer>>();
    ArrayList nodeValues = new ArrayList();
    if(root == null)
        return al;
 
    LinkedList current = new LinkedList();
    LinkedList next = new LinkedList();
    current.add(root);
 
    while(!current.isEmpty()){
        TreeNode node = current.remove();
 
        if(node.left != null)
            next.add(node.left);
        if(node.right != null)
            next.add(node.right);
 
        nodeValues.add(node.data);
        if(current.isEmpty()){
            current = next;
            next = new LinkedList();
            al.add(nodeValues);
            nodeValues = new ArrayList();
        }
 
    }
    return al;
}

Has Path Sum (Traversal)

Given a tree and a sum, returns true if there is a path from the root down to a leaf, such that adding up all the values along the path equals the given sum.

public boolean hasPathSum(int sum) { 
 return( hasPathSum(root, sum) ); 
} 

boolean hasPathSum(Node node, int sum) { 
  // return true if we run out of tree and sum==0 
  if (node == null) { 
    return(sum == 0); 
  } 
  else { 
  // otherwise check both subtrees 
    int subSum = sum - node.data; 
    return(hasPathSum(node.left, subSum) || hasPathSum(node.right, subSum)); 
  } 
} 

Binary Tree: Coding Problems

Binary Tree is a data struc­ture consisted of nodes con­tain­ing data and two ref­er­ences to other nodes, one on the left and one on the right.


Binary Tree con­sist of Nodes

class Node{
	int data; 
	Node left;
	Node right;	
	public Node(int data){
		this.data = data;
		left = null;
		right = null;
	}
       public setLeftNode(Node node){
		this.left = node;
	}
       public setRightNode(Node node){
		this.right = node;
	}  
}

Tree definitions:

Java Binary Tree Structure

public class BinaryTree { 
  private Node root;   // Root node pointer. Will be null for an empty tree. 
  
  private static class Node { 
    Node left; 
    Node right; 
    int data; 

    Node(int newData) { 
      left = null; 
      right = null; 
      data = newData; 
    } 
  } 
  // Create empty binary tree
  public void BinaryTree() { 
    root = null; 
  }
 
  public void insert(int data) { 
    root = insert(root, data); 
  } 
 private Node insert(Node node, int data) { 
    if (node==null) { 
      node = new Node(data); 
    } 
    else { 
      if (data <= node.data) { 
        node.left = insert(node.left, data); 
      } 
      else { 
        node.right = insert(node.right, data); 
      } 
    } 
    return(node); // in any case, return the new pointer to the caller 
  } 
}  

Oper­a­tions

Insert(int n) : Add a node with value n O(lgn)

Find(int n) : Find a node with value n O(lgn)

Delete (int n) : Delete a node with value n O(lgn)

Dis­play(): Prints the entire tree in increas­ing order O(n)

 

Classic Tree problems

Most of the solutions use two methods: a one-line OOP method that starts the computation, and a recursive method that does the real operation.

Size

Returns the number of nodes in the tree

public int size() { 
  return(size(root)); 
} 
private int size(Node node) { 
  if (node == null) return(0); 
  else { 
    return(size(node.left) + 1 + size(node.right)); 
  } 
} 

Max Depth

Returns the max root-to-leaf depth of the tree

public int maxDepth() { 
  return(maxDepth(root)); 
} 
private int maxDepth(Node node) { 
  if (node==null) { 
    return(0); 
  } 
  else { 
    int lDepth = maxDepth(node.left); 
    int rDepth = maxDepth(node.right); 
    return(Math.max(lDepth, rDepth) + 1); 
  } 
} 
  

Min value

Returns the min value in a non-empty binary search tree

public int minValue() { 
 return( minValue(root) ); 
} 

private int minValue(Node node) { 
  Node current = node; 
  while (current.left != null) { 
    current = current.left; 
  } 
  return(current.data); 
} 
  

Max value

Returns the max value in a non-empty binary search tree

public int maxValue() { 
 return( maxValue(root) ); 
} 

private int maxValue(Node node) { 
  Node current = node; 
  while (current.right != null) { 
    current = current.right; 
  } 
  return(current.data); 
} 
  

Inorder print of tree

Prints the node values in the "inorder" order

public void printInOrderTree() { 
 printInOrderTree(root); 
 System.out.println(); 
} 
private void printInOrderTree(Node node) { 
 if (node == null) return; 

 // left, node itself, right 
 printInOrderTree(node.left); 
 System.out.print(node.data + "  "); 
 printInOrderTree(node.right); 
} 

Postorderprint of tree

Prints the node values in the "postorder" order

public void printPostOrderTree() { 
 printPostOrderTree(root); 
 System.out.println(); 
} 
private void printPostOrderTree(Node node) { 
 if (node == null) return; 

 printPostOrderTree(node.left); 
 printPostOrderTree(node.right); 
 System.out.print(node.data + "  "); 
} 

PreOrder print of tree

Recursion

Prints the node values in the "preorder" order

public void printPreOrderTree() { 
 printPreOrderTree(root); 
 System.out.println(); 
} 
private void printPreOrderTree(Node node) { 
 if (node == null) return; 
 System.out.print(node.data + "  "); 
 printPreOrderTree(node.left); 
 printPreOrderTree(node.right); 

} 

Without recursion (Traversal)

public class Solution {
    public ArrayList<Integer> preorderTraversal(Node root) {
        ArrayList<Integer> returnList = new ArrayList<Integer>();
 
        if(root == null)
            return returnList;
 
        Stack stack = new Stack();
        stack.push(root);
 
        while(!stack.empty()){
            TreeNode n = stack.pop();
            returnList.add(n.val);
 
            if(n.right != null){
                stack.push(n.right);
            }
            if(n.left != null){
                stack.push(n.left);
            }
 
        }
        return returnList;
    }
   public void print(Node root){
          ArrayList<Integer> 
          list =  preorderTraversal(root);
          for(Integer item: list){
               System.out.println(item.data);	
         }  }
}

Print in Level order (Traversal)

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:

Given binary tree {3,9,20,#,#,15,7},

   
    4
   / \
  8  22
      /  \
   11   6

return its level order traversal as [[4], [8,22], [11,6]]

public ArrayList<ArrayList> levelOrder(TreeNode root) {
    ArrayList<ArrayList<Integer>> al = new ArrayList<ArrayList<Integer>>();
    ArrayList nodeValues = new ArrayList();
    if(root == null)
        return al;
 
    LinkedList current = new LinkedList();
    LinkedList next = new LinkedList();
    current.add(root);
 
    while(!current.isEmpty()){
        TreeNode node = current.remove();
 
        if(node.left != null)
            next.add(node.left);
        if(node.right != null)
            next.add(node.right);
 
        nodeValues.add(node.data);
        if(current.isEmpty()){
            current = next;
            next = new LinkedList();
            al.add(nodeValues);
            nodeValues = new ArrayList();
        }
 
    }
    return al;
}

Has Path Sum (Traversal)

Given a tree and a sum, returns true if there is a path from the root down to a leaf, such that adding up all the values along the path equals the given sum.

We'll define a "root-to-leaf path" to be a sequence of nodes in a tree starting with the root node and proceeding downward to a leaf (a node with no children). We'll say that an empty tree contains no root-to-leaf paths. So for example, the following tree has exactly four root-to-leaf paths: 
              5 
             / \ 
            4   8 
           /   / \ 
          11  13  4 
         /  \      \ 
        7    2      1 

Root-to-leaf paths: 
   path 1: 5 4 11 7 
   path 2: 5 4 11 2 
   path 3: 5 8 13 
   path 4: 5 8 4 1 

For this problem, we will be concerned with the sum of the values of such a path -- for example, the sum of the values on the 5-4-11-7 path is 5 + 4 + 11 + 7 = 27. 

public boolean hasPathSum(int sum) { 
 return( hasPathSum(root, sum) ); 
} 

boolean hasPathSum(Node node, int sum) { 
  // return true if we run out of tree and sum==0 
  if (node == null) { 
    return(sum == 0); 
  } 
  else { 
  // otherwise check both subtrees 
    int subSum = sum - node.data; 
    return(hasPathSum(node.left, subSum) || hasPathSum(node.right, subSum)); 
  } 
} 

Print Paths

Given a binary tree, prints out all of its root-to-leaf paths, one per line.

              5 
             / \ 
            4   8 
           /   / \ 
          11  13  4 
         /  \      \ 
        7    2      1 

Paths: 
   path 1: 5 4 11 7 
   path 2: 5 4 11 2 
   path 3: 5 8 13 
   path 4: 5 8 4 1 
public void printPaths() { 
  int[] path = new int[1000]; 
  printPaths(root, path, 0); 
} 

private void printPaths(Node node, int[] path, int pathLen) { 
  if (node==null) return; 

  // append this node to the path array 
  path[pathLen] = node.data; 
  pathLen++; 

  // it's a leaf, so print the path that led to here 
  if (node.left==null && node.right==null) { 
    printArray(path, pathLen); 
  } 
  else { 
  // otherwise try both subtrees 
    printPaths(node.left, path, pathLen); 
    printPaths(node.right, path, pathLen); 
  } 
} 

private void printArray(int[] ints, int len) { 
  int i; 
  for (i=0; i<len; i++) { 
   System.out.print(ints[i] + " "); 
  } 
  System.out.println(); 
} 

Create mirror of the tree

Changes the tree into its mirror image.

       
 So the tree... 
       4 
      / \ 
     2   5 
    / \ 
   1   3 

 is changed to... 
       4 
      / \ 
     5   2 
        / \ 
       3   1 
public void mirror() { 
  mirror(root); 
} 

private void mirror(Node node) { 
  if (node != null) { 
    // do the sub-trees 
    mirror(node.left); 
    mirror(node.right); 

    // swap the left/right pointers 
    Node temp = node.left; 
    node.left = node.right; 
    node.right = temp; 
  } 
} 

Update tree as a double tree

Changes the tree by inserting a duplicate node on each nodes's .left.

       
 So the tree... 
    2 
   / \ 
  1   3 

 Is changed to... 
       2 
      / \ 
     2   3 
    /   / 
   1   3 
  / 
 1 
public void doubleTree() { 
 doubleTree(root); 
} 

private void doubleTree(Node node) { 
  Node oldLeft; 

  if (node == null) return; 

  // do the subtrees 
  doubleTree(node.left); 
  doubleTree(node.right); 

  // duplicate this node to its left 
  oldLeft = node.left; 
  node.left = new Node(node.data); 
  node.left.left = oldLeft; 
} 

Median or kth element

Finding kth element in BST is quite simple. We know that all the elements in left subtree is smaller than all the elements in right subtree. If we count the number of elements in left and right subtree then we know in which subtree the required element exists and then we move to this subtree and repeat the same steps again. For example starting from root we are looking for 11th element. Lets say left subtree has 7 elements and right subtree has 6 elements.Then as the number 11 is greater than 7 we know that the 11th median exists in the right subtree. Now in the right subtree we look for (11 - 7 -1 = 3)rd element (Why?? because we have discarded left subtree). We proceed similarly in the new subtree until we get the kth median as the root.

The example described above can very well be described in recursive form. The code below is a complete program in recursive form.

 
//find kth element in a BST recursively
Node find_kth_element(Node tree, int k) {

 if(tree == null)
  return null;

 int count = 0;

 //count the nodes in left subtree
 count_nodes(tree.left, count);

 //check if the root is median
 if( k == count + 1)
  return tree;

 //check if median falls on left subtree
 else if (count >= k) {

  return find_kth_element(tree.left,k);
 }
 //the median falls on right subtree
 else {
  k = k - (count + 1);
  return find_kth_element(tree.right, k);
 }
}

We know that recursive solutions are not that efficient and it's always good to avoid it if it's possible. The problem however is equally simple in iterative form as well. The code below translates recursive form into iterative form.

//find kth element iteratively
Node find_kth_element_iterative(Node tree, int k) {
 if(tree == null)
  return null;

 Node node = tree;
 int count = 0;
 int pos = k;


 while(node != null) {
  count = 0;

  //count nodes on the left subtree
  count_nodes(node.left, count);

  //check if root is the median
  if( pos == count + 1)
   return node;

  //check if median falls on left subtree
  else if (count >= pos)
   node = node.left;

  //median falls on right subtree
  else {
   pos -= (count + 1);
   node = node.right;
  }

 }
 return null;
}

What's the complexity of above algorithms? While finding median You are moving along a path in the tree, so in the worst case it can be height of the tree (h) and also you are counting the number of nodes in left subtree at each step. Which requires O(n) time in the worst case. Thus the overall algorithm is O(nh).

How can you improve it? You can construct a tree with a count of elements in its subtree. If you do this the counting of number of nodes in left subtree takes O(1) time. Effectively the algorithm will reduce to O(h) algorithm. In case tree is balanced this is just O(log n).

   public String median() {
        int count = root.left.size + root.right.size + 1;
        count = (int) Math.floor(count/2);
        System.out.println("count="+count);
        return median(root, count);
    }
    private String median(Node n, int count) {
        if (n.size == count) return n.key;
        if (n.left!=null && n.right!=null)
        return median(n.left,count) + median(n.right,count);
        if  (n.left!=null)
            return median(n.left,count);
        if  (n.right!=null)
            return median(n.right,count);
        return"";
    }

Number of null nodes

  public int numNull() {
        return numNull(root);
    }
    private int numNull(Node n) {
        if (n==null) return 1;
        return numNull(n.left) + numNull(n.right);
    }

Length of the shortest path from root to a null node

Way 1: Recursion

    public int lenShortestPathToNull() {
        return lenShortestPathToNull(root);
    }
    public int lenShortestPathToNull(Node node) {
        if (node==null) return 1;
        return Math.min(lenShortestPathToNull(node.left), lenShortestPathToNull( node.right));
    }

Way 2: Loop

    public class Item {
        public Node node;
        public int count;

        private Item(Node node, int count) {
            this.node = node;
            this.count = count;
        }
    }
     public int lenShortestPathToNull() {
        if (root==null) new IllegalArgumentException("Illegal argument");
        int count = 0;
        Node cur = root;

        LinkedList queue = new LinkedList();
        Item item = new Item(root, 0);
        queue.add(item);
        while(queue.size()!=0){
            Item n = queue.poll();
            if (n.node.left == null) return n.count;
            if (n.node.right == null) return n.count;
            item = new Item(n.node.left, n.count+1);
            queue.add(item);
            item = new Item(n.node.right, n.count+1);
            queue.add(item);
        }
        return 0;
    }

Merge of two binary trees

If the given symbol table contains keys that is already in this symbol table, merge overwrites those keys' values with the values in the given symbol table.

    public void merge(BST bst) {
        merge(bst.root);
    }

    public void merge(Node n) {
        put(n.key, n.val);
        if (n.left!=null) merge(n.left);
        if (n.right!=null) merge(n.right);
    }

    public void put(String key, Integer val) {
        if (key == null) throw new NullPointerException("first argument to put() is null");
        root = put(root, key, val);
    }

    private Node put(Node x, String key, Integer val) {
        if (x == null) return new Node(key, val);
        int cmp = key.compareTo(x.key);
        if (cmp < 0) x.left = put(x.left, key, val);
        else if (cmp > 0) x.right = put(x.right, key, val);
        else x.val = val;
        x.size = 1 + size(x.left) + size(x.right);
        return x;
    }

Return closest key from BST

 public String closest(String key) {
        if (key=="" || key==null || root==null) return null;
        if (get(key)!=null) return (key);
        ArrayList arr= new ArrayList();
        closest(root, key, arr);
        int min=Integer.MAX_VALUE;
        String kkey =null;
        Collections.sort(arr);
        for(String item: arr){
            if (min>Math.abs(key.compareTo(item))) {
                kkey = item;
                min = Math.abs(key.compareTo(item));
            }
        }
        //recursion
         return kkey;
    }

    public void closest(Node node, String key, ArrayList arr) {
        if (node.key.compareTo(key)<0) {
            // go to right side
            if (node.right== null) {
                //last node, which may be a parent;  no pair
                if (arr.size()==0) arr.add(node.key);  
                return;
            }
            else { if (node.right.key.compareTo(key)>0) {
                // add pair if key may be between nodes keys
                arr.add(node.key);
                arr.add(node.right.key);
                if (node.right.left!=null) {
                    //try to find new sides
                    closest(node.right.left, key, arr); 
                } else {
                    //we are good, no additional pairs;  just return
                    return;}
            }
                else {
                    // no pair, both node's keys smaller than our key                    
                    closest(node.right, key, arr);
                }
            }

        } else {
            if (node.left== null) {if (arr.size()==0)  arr.add(node.key); return;}
            else { if (node.left.key.compareTo(key)<0) {
                // add pair if key may be between nodes keys
                arr.add(node.key);
                arr.add(node.left.key);
                if (node.left.right!=null) closest(node.left.right, key, arr); else return; }
                else closest(node.left, key, arr);
            }

        }

    }

Second max key

   
public String SecondMax(){
        if (root==null) return null;
        return SecondMax(root, null, null);
    }
    public String SecondMax(Node n, String max, String secondMax){
        if (n==null || n.key==null) return secondMax;
        if (max==null || max.compareTo(n.key)<0)
        {secondMax = max;
        max = n.key;}
        else {
            if (secondMax==null || secondMax.compareTo(n.key)<0)
                secondMax=n.key;
        }

        if (n.right!=null)
            return SecondMax(n.right, max, secondMax);
        else
            return SecondMax(n.left, max, secondMax);
    }