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;
}
}
}
Top comments (0)