Session 27: Binary Trees

Original Session

Date: 05 Jan 2025

Topic: Trees

Concept: Tree has node with multiple path forward.

Concept: Binary tree traversals.

Inorder - Left→Root→Right, Preorder - Root → Left → Right, Postorder - Left →Right → Root

Concept: Height = Depth of the BT, is maximum distance from any leaf node to root node.

Or number of nodes from root node to the farthest leaf node including root node.

Concept: Diameter of the tree, Number of nodes in the longest path between any two nodes.

Diameter of Node = Height of Left Node + Height of Right Node + 1

Max Diameter of Node = Max(LeftDiameter, RightDiamere, CurrentDiameter)

Case1: Diameter Pass through root.

Case 2: Diameter may not pass through root.

Programs

  1. 94. Binary Tree Inorder Traversal
    1. leetcode here
    public List<Integer> inorderTraversal(TreeNode root) {
        
        List<Integer> list = new ArrayList();
        traverse(root, list);
        return list;
    }

    void traverse(TreeNode root, List<Integer> list) {

        if (root == null) {
            return;
        }

        traverse(root.left, list);
        list.add(root.val);
        traverse(root.right, list);
    }

  1. 144. Binary Tree Preorder Traversal
    1. leetcode here
    void traverse(TreeNode root, List<Integer> list) {

        if (root == null) {
            return;
        }
        list.add(root.val);
        traverse(root.left, list);
        traverse(root.right, list);
    }

  1. 145. Binary Tree Postorder Traversal
    1. leetcode here
    void traverse(TreeNode root, List<Integer> list) {

        if (root == null) {
            return;
        }
        
        traverse(root.left, list);
        traverse(root.right, list);
        list.add(root.val);
    }

  1. 222. Count Complete Tree Nodes
    1. leetcode here
    public int countNodes(TreeNode root) {
        
        if (root == null) {
            return 0;
        }

        return countNodes(root.left) + countNodes(root.right) + 1;
}

  1. Count Leaves in Binary Tree
    1. GFG here
    int countLeaves(Node root) {
        
        if (root == null) {
	        return 0;
	    }
	    
	    if (root.left == null && root.right == null) {
	        return 1;
	    }
	    
	    return countLeaves(root.left) + countLeaves(root.right);
}

  1. Sum of Leaf Nodes
    1. GFG here
    int leafSum(Node root) {
        // Your code here
        
        if (root == null) {
	        return 0;
	    }
	    
	    if (root.left == null && root.right == null) {
	        return root.data;
	    }
        
        return leafSum(root.left) + leafSum(root.right);
    }

  1. 404. Sum of Left Leaves
    1. leetcode here
    	
		int ans = 0;

    private void travese(TreeNode root) {

        if (root == null) {
            return;
        }

        travese(root.left);
        travese(root.right);

        if (root.left != null 
        && (root.left.left == null && root.left.right == null)) {
            ans += root.left.val;
        }
    }

    public int sumOfLeftLeaves(TreeNode root) {
        travese(root);
        return ans;
    }

  1. 872. Leaf-Similar Trees
    1. leetcode here
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {

        List<Integer> list1 = new ArrayList();
        List<Integer> list2 = new ArrayList();
        
        leafeNodesList(root1, list1);
        leafeNodesList(root2, list2);

        return list1.equals(list2);
    }

    void leafeNodesList(TreeNode root, List<Integer> list) {
        
        if (root == null) {
            return;
        }

        leafeNodesList(root.left, list);
        leafeNodesList(root.right, list);

        if (root.left == null && root.right == null) {
            list.add(root.val);
        }        
    }

  1. 104. Maximum Depth of Binary Tree
    1. leetcode here
    public int maxDepth(TreeNode root) {
        return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }