DEV Community

Prashant Mishra
Prashant Mishra

Posted on • Edited on

Binary Tree

Types of trees

Problems:

Left view of the binary tree

TC: O(n) , as we will be traversing n nodes of the tree

class Tree{ int currentMax = Integer.MIN_VALUE; public ArrayList<Integer> leftView(Node node){ ArrayList<Integer> list = new ArrayList<>(); traverseForLeftView(node,0,list); return list; } public void traverseForLeftView(Node node,int level,ArrayList<Integer> list){ if(node==null) return; if(level > currentMax){ list.add(node.data); currentMax = level; } traverseForLeftView(node.left,level+1,list); traverseForLeftView(node.right,level+1,list); } }
Enter fullscreen mode Exit fullscreen mode

Bottom view of binary tree

TC : O(NlogN) + O(N) ~ O(NlogN), since we are using TreeMap it will take nlogn time for sorting entries based on keys

class Solution { //Function to return a list containing the bottom view of the given tree. public ArrayList <Integer> bottomView(Node root) { //we will use map and Queue for this ArrayList<Integer> list = new ArrayList<>(); Map<Integer,Integer> map = new TreeMap<>(); Queue<Pair> q = new LinkedList<>(); if(root==null) return null; q.add(new Pair(root,0)); //root is at level 0 while(!q.isEmpty()){ Pair p = q.remove(); Node n = p.getNode(); int level = p.getLevel(); map.put(level,n.data); if(n.left!=null){ q.add(new Pair(n.left,level-1)); } if(n.right!=null){ q.add(new Pair(n.right,level+1)); } } for(Map.Entry<Integer,Integer> e : map.entrySet()) list.add(e.getValue()); return list; } } class Pair{ Node node; int level; public Pair(Node n, int l){ this.node = n; this.level = l; } public Node getNode(){ return this.node; } public int getLevel(){ return this.level; } }
Enter fullscreen mode Exit fullscreen mode

Top view of binary tree

TC : o(nlogn) for using TreeMap<>();

class Solution { //Function to return a list of nodes visible from the top view  //from left to right in Binary Tree. static ArrayList<Integer> topView(Node root) { // we can solve it with the same depth first search approach we used for bottom view of the tree ArrayList<Integer> list = new ArrayList<>(); Map<Integer,Integer> map = new TreeMap<>(); Queue<Pair> q = new LinkedList<>(); q.add(new Pair(root,0)); while(!q.isEmpty()){ Pair p = q.remove(); Node n = p.getNode(); int level = p.getLevel(); if(!map.containsKey(level)) map.put(level,n.data); if(n.left!=null) q.add(new Pair(n.left,level-1)); if(n.right!=null) q.add(new Pair(n.right,level +1)); } for(Map.Entry<Integer,Integer> e : map.entrySet()) list.add(e.getValue()); return list; } } class Pair{ Node node; int level; public Pair(Node n, int l){ this.node = n; this.level = l; } public Node getNode(){ return this.node; } public int getLevel(){ return this.level; } }
Enter fullscreen mode Exit fullscreen mode

maximum width in a binary tree

TC: O(n), as we are traversing n nodes of the tree

import java.util.*; public class Solution { public static int getMaxWidth(TreeNode root) { if(root ==null) return 0; // Write your code here. //this we can solve using depth first search algorithm and keep track of  //max no. of nodes in a given level Queue<TreeNode> q = new LinkedList<>(); int max = 0; q.add(root); while(!q.isEmpty()){ int n = q.size(); max = Integer.max(max,n); for(int i =0;i<n;i++){ TreeNode node = q.remove(); if(node.left!=null) q.add(node.left); if(node.right!=null) q.add(node.right); } } return max; } }
Enter fullscreen mode Exit fullscreen mode

Maximum width of a binary tree when null nodes are also considered between leftMost node and rightMost node at each level

TC: O(N) where n is the no. of nodes

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public int widthOfBinaryTree(TreeNode root) { //we will use strivers approach for solving this problem int maxWidth = 0; Queue<Pair<TreeNode,Integer>> q = new LinkedList<>(); if(root== null) return 0; q.add(new Pair(root,0)); while(!q.isEmpty()){ int size = q.size(); int first = 0; int last =0; int minIndex = q.peek().getValue(); for(int i =0;i<size;i++){ Pair<TreeNode,Integer> p = q.remove(); TreeNode n = p.getKey(); int index = p.getValue()-minIndex; if(i ==0) first = index; if(i ==size-1) last = index; if(n.left!=null) q.add(new Pair(n.left,2*index +1)); if(n.right!=null) q.add(new Pair(n.right,2*index +2)); } maxWidth = Integer.max(maxWidth,last-first +1); } return maxWidth; } }
Enter fullscreen mode Exit fullscreen mode

Mirror a binary tree

TC: O(n), where n is no. of nodes in the tree

class Solution { // Function to convert a binary tree into its mirror tree. void mirror(Node node) { dfs(node); } public Node dfs(Node node){ if(node ==null) return node; Node left = dfs(node.left); Node right = dfs(node.right); Node temp = node.left; node.left = right; node.right = temp; return node; } }
Enter fullscreen mode Exit fullscreen mode

Symmetric tree i.e check if tree is mirror of itself or not

TC: O(N)

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public boolean isSymmetric(TreeNode root) { return preorder(root,root); } public boolean preorder(TreeNode node, TreeNode fode){ if(node==null && fode ==null) return true; if(node==null && fode!=null || node!=null && fode==null || node.val!=fode.val) return false; return preorder(node.left,fode.right) && preorder(node.right,fode.left); } }
Enter fullscreen mode Exit fullscreen mode

Construct Unique Binary tree from inorder and preorder array

TC: O(N)

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { Map<Integer,Integer> in = new HashMap<>(); for(int i =0;i<inorder.length;i++) in.put(inorder[i],i); return generateTree(0,in.size()-1,0,postorder.length-1,in,postorder); } public TreeNode generateTree(int inmin, int inmax,int pomin,int pomax,Map<Integer,Integer> in, int[] po){ if(inmin > inmax || pomin > pomax ) return null; int val = po[pomax];//last element of postorder is the root element TreeNode root = new TreeNode(val); int rIndex = in.get(val); // we have got the index of root element in inorder //note //for left part, inorder range will be inmin,rIndex-1 //for right part, inorder range will be rIndex+1,inmax //also, //for left part, postorder range will be pmin,lengthOfInOrderRange i.e pomin+rIndex-inmin-1 //for right part, postorder range will be (lengthOfInOrderRange)+1,pmax i.e pomin+rIndex-inmin root.left = generateTree(inmin,rIndex-1,pomin,pomin+rIndex-inmin-1,in,po); root.right = generateTree(rIndex+1,inmax,pomin+rIndex-inmin,pomax-1,in,po); return root; } }
Enter fullscreen mode Exit fullscreen mode

Construct unique binary tree from inorder and preorder of the tree

TC: O(N)

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { Map<Integer,Integer> in = new HashMap<>(); for(int i =0;i<inorder.length;i++){ in.put(inorder[i],i); } return generateTree(0,inorder.length-1,0,preorder.length-1,in,preorder); } public TreeNode generateTree(int inmin,int inmax,int pmin,int pmax,Map<Integer,Integer> in,int[] pre){ if(inmin>inmax || pmin > pmax) return null; int val = pre[pmin]; TreeNode node = new TreeNode(val); int rIndex = in.get(val); //note: //for left subtree, inorder range will be inmin,rIndex-1 //for right substrr, inorder range will be rIdnex+1,pmax //for left subtree, preorder range will be pmin+1, pmin+1+rIndex-inmin-1 //for right subtree, preorder range will be pmin+1+rIndex-inmin,pmax node.left = generateTree(inmin,rIndex-1,pmin+1,pmin+1+rIndex-inmin-1,in,pre); node.right = generateTree(rIndex+1,pmax,pmin+1+rIndex-inmin,pmax,in,pre); return node; } }
Enter fullscreen mode Exit fullscreen mode

Maximum path sum

TC: O(N)

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { int max =Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { maxPath(root); return max; } public int maxPath(TreeNode node){ if(node==null) return 0; int left = Integer.max(0,maxPath(node.left)); int right = Integer.max(0,maxPath(node.right)); max = Integer.max(max,node.val + left+right); return node.val + Integer.max(left,right); } }
Enter fullscreen mode Exit fullscreen mode

Boundary traversal of binary tree

TC: O(N)

/************************************************************ Following is the Binary Tree node structure: class TreeNode { int data; TreeNode left; TreeNode right; TreeNode(int data) { this.data = data; this.left = null; this.right = null; } } ************************************************************/ import java.util.*; public class Solution { public static ArrayList<Integer> traverseBoundary(TreeNode root){ ArrayList<Integer> list = new ArrayList<>(); ///first left part , then leaf nodes then right part in reverse Order if(root == null) return list; if(root.left!=null || root.right!=null) list.add(root.data); //left part getLeft(root,list); //leaf nodes preOrder(root,list); //right view in reverseOrder getRight(root,list); return list; } public static void getRight(TreeNode node,ArrayList<Integer> list){ ArrayList<Integer> temp = new ArrayList<>(); TreeNode currentNode = node.right; while(currentNode!=null){ if(currentNode.left!=null || currentNode.right!=null) temp.add(currentNode.data); if(currentNode.right!=null) currentNode = currentNode.right; else currentNode = currentNode.left; } int i =temp.size()-1; for(;i>=0;i--) list.add(temp.get(i)); } public static void preOrder(TreeNode node, ArrayList<Integer> list){ if(node == null) return; if(node.left==null && node.right ==null) { list.add(node.data); return; } preOrder(node.left,list); preOrder(node.right,list); } public static void getLeft(TreeNode node,ArrayList<Integer> list){ TreeNode currentNode = node.left; while(currentNode!=null){ if(currentNode.left!=null || currentNode.right!=null) list.add(currentNode.data); if(currentNode.left!=null) currentNode = currentNode.left; else currentNode = currentNode.right; } } }
Enter fullscreen mode Exit fullscreen mode

Top comments (0)