Day 4: Binary Tree-II

Day 4: Binary Tree-II

If you haven't read the previous article in this series, Please find the link here.

Patterns

  • Traversal(s)

image.png

Level-order Traversal of a Tree

Given a binary tree, find its level order traversal.
Note: Level order traversal of a tree is breadth-first traversal for the tree. image.png

We just begin traversing the tree from the root and continuing to add the left and right children of nodes to the queue. To visit all of the nodes in a tree, we dequeue each node and output its value.

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {

        List<List<Integer>> output = new LinkedList<>();
        if(root==null) return output;
        Queue<TreeNode> nodes = new LinkedList<>();
        nodes.add(root);
        while(nodes.size() > 0){
            int n = nodes.size();
            List<Integer> rows = new ArrayList<>();

            for(int i=0; i<n; i++){
                TreeNode temp = nodes.remove();
                rows.add(temp.val);

                if(temp.left!=null){
                    nodes.add(temp.left);
                }

                if(temp.right!=null){
                    nodes.add(temp.right);
                }
            }

            output.add(new ArrayList<>(rows));
        }

        return output;
    }
}

Zig Zag Level-order Traversal of a Tree

Same as the above, level order traversal, just push the elements at each level in either as same or in reverse in alternative.

image.png

public List<List<Integer>> zigzagLevelOrder1(TreeNode root) {
    List<List<Integer>> ret = new ArrayList<>();
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    int l = 0;
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            if (node != null) {
                level.add(node.val);
                queue.add(node.left);
                queue.add(node.right);
            }
        }
        if (!level.isEmpty()) {
            if (l % 2 == 1) {
                Collections.reverse(level);
            }
            ret.add(level);
        }
        l++;
    }
    return ret;
 }

Boundary Traversal of a Tree

Given a binary tree, print boundary nodes of the binary tree Anti-Clockwise starting from the root. The boundary includes the left boundary, leaves, and right boundary in order without duplicate nodes. (The values of the nodes may still be duplicates.)

image.png

The left boundary is defined as the path from the root to the leftmost node. The right boundary is defined as the path from the root to the right-most node. If the root doesn’t have a left subtree or right subtree, then the root itself is a left boundary or right boundary. Note this definition only applies to the input binary tree and does not apply to any subtrees. The left-most node is defined as a leaf node you could reach when you always firstly travel to the left subtree if it exists. If not, travel to the right subtree. Repeat until you reach a leaf node. The right-most node is also defined in the same way as the left and right exchanged.

//Code credits: GFG
// Java program to print boundary traversal of binary tree

import java.io.*;
import java.util.*;

class BinaryTree {
    Node root;
    /* A binary tree node has data, pointer to left child
and a pointer to right child */
    static class Node {
        int data;
        Node left, right;
        Node(int d)
        {
            data = d;
            left = null;
            right = null;
        }
    }

    private boolean isLeaf(Node node)
    {
        if (node.left == null && node.right == null) {
            return true;
        }
        return false;
    }

    private void addLeftBound(Node root,
                            ArrayList<Integer> ans)
    {
        // Go left left and no left then right but again
        // check from left
        root = root.left;
        while (root != null) {
            if (!isLeaf(root)) {
                ans.add(root.data);
            }

            if (root.left != null) {
                root = root.left;
            }
            else {
                root = root.right;
            }
        }
    }

    private void addRightBound(Node root,
                            ArrayList<Integer> ans)
    {
        // Go right right and no right then left but again
        // check from right
        root = root.right;
        // As we need the reverse of this for Anticlockwise
        Stack<Integer> stk = new Stack<>();
        while (root != null) {
            if (!isLeaf(root)) {
                stk.push(root.data);
            }
            if (root.right != null) {
                root = root.right;
            }
            else {
                root = root.left;
            }
        }

        while (!stk.isEmpty()) {
            ans.add(stk.peek());
            stk.pop();
        }
    }

    // its kind of inorder
    private void addLeaves(Node root,
                        ArrayList<Integer> ans)
    {
        if (root == null) {
            return;
        }

        if (isLeaf(root)) {
            ans.add(root.data); // just store leaf nodes
            return;
        }

        addLeaves(root.left, ans);
        addLeaves(root.right, ans);
    }

    ArrayList<Integer> boundary(Node root)
    {
        ArrayList<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }

        if (!isLeaf(root)) {
            ans.add(root.data); // if leaf then its done by
                                // addLeaves
        }

        addLeftBound(root, ans);
        addLeaves(root, ans);
        addRightBound(root, ans);
        return ans;
    }
}

Height of Tree

Given a binary tree, find its height.

In order to find a tree height, If we carefully observe, the number of levels in a tree is equal to the height of the tree.

But however, this way of approach is not viable as it takes an additional stack (or) queue to add and delete the tree nodes. So we will do a recursive way to find out the height of the tree. At each node, we will find the height of the sub-trees(Left Sub-Tree and Right Sub-Tree).

class Solution {
    int height(Node node) 
    {
        // code here 
        if(node == null){
            return 0;
        }

        int left = height(node.left);
        int right = height(node.right);

        return Math.max(left, right) + 1;
    }
}

Leaf at same level

Given a Binary Tree, check if all leaves are at the same level or not.

image.png

Simply find the either left most or right most leaf node level, and for every leaf node level check if the current leaf node level is equal to already found the leaf node level. If equal continue, else return false.

class Solution{
   public static int level = 0; 
    //isSameLevel() will check whether all leaves of the binary tree is at same level or not  
    public boolean isSameLevel(Node temp, int currentLevel ) {  

        //Check whether tree is empty  
        if(root == null){  
          return true;  
        }  
        else {  
            //Checks whether node is null  
            if(temp==null)  
                return true;  

            if(temp.left == null && temp.right == null) {  
                //If first leaf is encountered, set level to current level  
                if(level == 0) {  
                    level = currentLevel ;  
                    return true;  
                }  
                //Checks whether the other leaves are at same level of that of first leaf  
                else   
                   return (level == currentLevel) ;  
             }  

            //Checks for leaf node in left and right subtree recursively.  
            return  (isSameLevel(temp.left, currentLevel + 1) && isSameLevel(temp.right, currentLevel + 1)) ;  
         }  
    }  
}

Mirror of the Tree

Given the root of a binary tree, invert the tree, and return its root.

image.png

We can do this in both recursive and iterative ways, Just visit the left and right subtrees simultaneously and then swap the nodes of subtrees. The same question can be asked to check if the given tree is a mirror tree or not. At that, just visit the left subtree and the right subtree and check if both values are the same, I.e for left node values equal to right node value and vice versa.

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null)
            return null;
        swap(root);
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    void swap(TreeNode root) {
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}

Is Balanced Tree

Given a binary tree, determine if it is height-balanced.
Note: A binary tree in which the left and right subtrees of every node differ in height by no more than 1.

image.png

This tree is not a balanced tree.

The brute force solution is to find the height of each node and to check if the nodes Height of Left Sub Tree and Height of Right Sub Tree does differ in more than one. But calling the height at each node is not a viable option as it takes O(N), and another O(N) for the general traversal of the tree.

An efficient method to solve this problem is by finding the height of the tree, but checking if the height of the left sub-tree and the height of the right sub-tree differ in more than one, then return and carry -1 forward.

class Solution {
    public boolean isBalanced(TreeNode root) {
        return dfsHeight(root) != -1;
    }
    int dfsHeight(TreeNode root){
        if(root == null)
            return 0;
        int leftHeight = dfsHeight(root.left);
        if(leftHeight == -1) return -1;
        int rightHeight = dfsHeight(root.right);
        if(rightHeight == -1) return -1;

        if(Math.abs(leftHeight - rightHeight) >1 ) return -1;
        return Math.max(leftHeight,rightHeight) +1;
    }
}

Convert Tree to Sum Tree

Given a Binary Tree where each node can have positive or negative values. Convert this to a tree where each node contains the sum of the left and right sub-trees of the original tree. The values of leaf nodes are changed to 0.

image.png

class Solution{

    static int MakeSumTreehelper(Node root){
        if(root==null) return 0;

        int a = helper(root.left);
        int b = helper(root.right);

        int x = root.data;

        root.data = a+b;

        return a+b+x;
    }
    public void toSumTree(Node root){
         MakeSumTreehelper(root);
    }
}

Is valid Sum Tree

Given a Binary Tree. Return true if, for every node X in the tree other than the leaves, its value is equal to the sum of its left subtree's value and its right subtree's value. Else return false.

image.png

Using recursion, we can easily solve this problem. The goal is to travel the tree in Post-Order. Check whether the value of each non-leaf node is equal to the sum of all items in its left and right subtrees. If this relationship does not hold for any node, the binary tree cannot be a sum tree.

    public int isSumTree(Node root)
    {
        if (root == null) {
            return 0;
        }

        if (root.left == null && root.right == null) {
            return root.key;
        }

        int left = isSumTree(root.left);
        int right = isSumTree(root.right);

        if (left != Integer.MIN_VALUE && right != Integer.MIN_VALUE &&
                root.key == left + right) {
            return 2 * root.key;
        }

        return Integer.MIN_VALUE;
    }

If the above function isSumTree(root) returns the Minimum value of the integer, then it does not satisfies the Sum-Tree condition.