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);
    }
}

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;
    }
}

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;
    }
}

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;  
    }
}

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;
    }
}

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;
    }

}

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);
    }
}

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;


    }
}

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;
    }
}

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);
    } 
}

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;
        }
    }
}