Trees Based Problems

Binary Trees

Problem Type - Traversal

-->

Find the distance between the farthest two elements in a binary tree.

- nra October 19, 2017 in United States | Flag 
Facebook Software Engineer Algorithm

-->

Given a binary tree, print the path that has the maximum path sum.

Pre -Order

By Recursion

By Iteration

In -Order

By RecursionBy Iteration

Find predecessor of  node in binary tree in ,In order traveral ?

Find successor of  node in binary tree in ,in order traversal ?

Post -Order

By Recursion

By Iteration

Find predecessor of  node in binary tree in ,post order traversal ?

Find successor of  node in binary tree in ,post order traversal ?

Level -Order

Zig Zag Spiral -Order

Problem Type - Search

DFS-Depth First Search

BFS - Breadth First Search 

Problem Type - Deletion /Insertion of a node

Deletion of a Node

case 1

case 2

case 3

case 4

Insertion of Node

case 1

case 2

case 3

case 4

Problem Type - Height/Depth/Diameter/Longest path /print all path  of a Binary Tree

1) Print all path of tree

Problem Type - Print/count/sum of all nodes leaf nodes of a Binary Tree

--

Problem Type - max/min node of a Binary Tree

Preview:

 // Prints all paths to leaf  
      public static void printPaths(TreeNode root, int[] path, int len) {  
             if(root == null) return;    
                     path[len] = root.data;  
                  len++;  
                  if(root.left==null && root.right ==null){  
                       // leaf node is reached  
                     printArray(path,len);  
                     return;  
                  }  
                     printPaths(root.left,path,len);  
                     printPaths(root.right,path,len);  
      }  
      public static void printArray(int[] path,int len)  
       {  
           for (int i = 0; i < len; i++) {  
                 System.out.print(" "+path[i]);  
                 }  
                 System.out.println();  
       }  

 // Prints al

--
2) Count leaf nodes
--

 //count leaf nodes  
      public static int countLeafNodes(TreeUtils.Node root){  
           if(root == null) return 0;    
           if(root.left ==null && root.right == null)  
         {    
                count++;  
                //System.out.println("count is :"+count+" "+root.data);  
         }  
           countLeafNodes(root.left);  
           countLeafNodes(root.right);  
           return count;  
      }  

--
3) Maximum node of Tree

public class MaxElementOfTree {  
      //Maximum node of tree  
      public static int getMaxElement(Node rooTNode) {  
           int max = Integer.MIN_VALUE;  
           int value = 0;  
           int leftValue = 0 ;       
           int rightValue = 0;  
           if(rooTNode != null){  
                value = rooTNode.data;  
                leftValue = getMaxElement(rooTNode.left);       
                rightValue = getMaxElement(rooTNode.right);  
           }  
           if(leftValue >rightValue){  
                max = leftValue;  
           }else{  
                max = rightValue;  
           }  
           if(max 

--

--


6) Traversals
--

Preview:

package com.vidushi.takshila.tree;  
 import java.util.ArrayList;  
 import java.util.Collections;  
 import java.util.Stack;  
 public class Traversal {  
      public static void main(String[] args) {  
         TreeUtils.Node root = TreeUtils.createBinaryTree();  
         preOrder(root);  
         inOrder(root);  
         postOrder(root);  
      }  
      public static void preOrder(TreeUtils.Node root){  
            if (root == null) return;  
            System.out.print("  "+root.data);  
            if(root.left != null) preOrder(root.left);  
            if(root.right != null)preOrder(root.right);  
      }  
      public static void inOrder(TreeUtils.Node root){  
            if (root == null) return;  
            if(root.left != null) inOrder(root.left);  
            System.out.print("  "+root.data);  
            if(root.right != null)inOrder(root.right);  
      }  
      public static void postOrder(TreeUtils.Node root){  
            if (root == null) return;  
            if(root != null) {  
              postOrder(root.left);  
              postOrder(root.right);  
              System.out.print("  "+root.data);  
            }  
      }  
 }  

--

--

8) Spiral Traversal
--

--
9) Print leaf node
--

--
10) Lateral inversion of tree
--

--

11) Lowest common ancestor of Binary tree

12) Create a balanced binary tree

13) Minimum depth on Binary Tree

14) Level Order Traversal 

15) Recover Binary Search Tree

16) Find n the largest element from a given binary tree

17) Total number of unique binary search trees

18) How to print all diagonal sums for a given binary search tree

19) Populate next right ptr  in a binary tree

20) Spiral level traversal of a binary tree

21) Check if binary tree is symmetric or non symmetric

22) Converting binary tree to binary search tree without changing spatial structure

23) Check if binary tree is balanced

24) Trie insert and search

25) Serialize and Deserialize binary Tree


26) Serialize and Deserialize binary Search Tree O(n) time

27) Huffman Coding


28) Adaptive Huffman Coding Tree

29) Adaptive Huffman Coding Tree -2

30) Serialize and Deserialize a Binary Tree

31)Width if binary Tree

32) Rebuild binary tree from inorder to preorder

33) Height of binary tree

34)Given a binary tree, print the path that has the maximum path sum. 

-->

1. 
   

 package com.vidushi.takshila.tree;  
 public class TreeUtils {  
        static class Node{  
                Node left;  
                Node right;  
                int data;       
                public Node(int data){  
                     this.data = data;  
                }  
           }  
           public static Node createBinaryTree(){  
                 Node rootNode =new Node(40);  
                 Node node20=new Node(20);  
                 Node node10=new Node(10);  
                 Node node30=new Node(30);  
                 Node node60=new Node(60);  
                 Node node50=new Node(50);  
                 Node node70=new Node(70);  
                 rootNode.left=node20;  
                 rootNode.right=node60;  
                 node20.left=node10;  
                 node20.right=node30;  
                 node60.left=node50;  
                 node60.right=node70;  
                 return rootNode;  
           }  
 }