Session 28: Binary Trees 2

Original Session

Date: 09 Jan 2025

Topic: Trees

Concept: Height of Binary Tree = max(left, right) + 1

Concept: Diameter of Binary Tree currentDiameter = (leftHight + rightHight)

Concept: Maximum Diameter of Binary Tree max(leftDiameter, rightDiameter, currentDiameter)

Concept: Height balanced Tree, for each node in tree “diff(leftH, rightH) > 1”

Programs

543. Diameter of Binary Tree

leetcode here

wpublic int diameterOfBinaryTree(TreeNode root) {

        // Height = Number of nodes including root node till the farthest leaf node in the tree.
        // can be calculated as Max(leftNode, rightNode) + 1;

        // Diameter = Maximum edges in the path which connects fartherst leaf nodes.
        // Can be sum of leftHight and rightHeight to include itself.
        // But when actual diameter is not going throught root, we might miss the actual diamter,
        // to avoid that we have to calculate diameter for leftNode and rightNode,
        // Then consider maximum between left, right and current diameter.

        if (root == null) {
            return 0;
        }

        NodeInfo nodeInfo = diamter(root);
        return nodeInfo.diameter;

    }

    NodeInfo diamter(TreeNode root) {

        if (root == null) {
            return new NodeInfo(0, 0);
        }

        NodeInfo leftNodeInfo = diamter(root.left);
        NodeInfo rightNodeInfo = diamter(root.right);
        int tempDiameter = leftNodeInfo.height + rightNodeInfo.height;
        int currDiameter = Math.max(tempDiameter, Math.max(leftNodeInfo.diameter, rightNodeInfo.diameter));
        int currHeight = Math.max(leftNodeInfo.height, rightNodeInfo.height) + 1;
        return new NodeInfo(currHeight, currDiameter);
    }

    private class NodeInfo {
        
        NodeInfo(int height, int diameter) {

            this.height = height;
            this.diameter = diameter;
        }
        int height = 0;
        int diameter = 0;
    }

110. Balanced Binary Tree

leetcode here

public boolean isBalanced(TreeNode root) {
        
        if (root == null) {
            return true;
        }

        int leftH = height(root.left);
        int rightH = height(root.right);

        if (Math.abs(leftH - rightH) > 1) {
            return false;
        }

        return isBalanced(root.left) && isBalanced(root.right);
    }

    int height(TreeNode root) {

        if (root == null) {
            return 0;
        }

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

100. Same Tree

leetcode here

public boolean isSameTree(TreeNode p, TreeNode q) {
        
        if (p == null && q == null) {
            return true;
        }

        if (p == null) {
            return false;
        }

        if (q == null) {
            return false;
        }

        if (p.val != q.val) {
            return false;
        }

        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

572. Subtree of Another Tree

leetcode here

public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        
        if (subRoot == null) {
            return true;
        }

        if (root == null) {
            return false;
        }
        
        if (root.val == subRoot.val && isSameTree(root, subRoot)) {
            return true;
        }

        return isSubtree(root.left, subRoot) 
            || isSubtree(root.right, subRoot);
    }

    private boolean isSameTree(TreeNode p, TreeNode q) {
        
        if (p == null && q == null) {
            return true;
        }

        if (p == null) {
            return false;
        }

        if (q == null) {
            return false;
        }

        if (p.val != q.val) {
            return false;
        }

        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

101. Symmetric Tree

leetcode here

public boolean isSymmetric(TreeNode root) {
        
        if (root == null) {
            return false;
        }

        return isSymmetric(root.left, root.right);
    }

    public boolean isSymmetric(TreeNode p, TreeNode q) {

     if (p == null && q == null) {
            return true;
        }

        if (p == null) {
            return false;
        }

        if (q == null) {
            return false;
        }

        if (p.val != q.val) {
            return false;
        }

        return isSymmetric(p.left, q.right) && isSymmetric(p.right, q.left);   
    }

257. Binary Tree Paths

leetcode here

public List<String> binaryTreePaths(TreeNode root) {
        
        List<String> paths = new ArrayList();
        func(root, "", paths);
        return paths;
    }

    void func(TreeNode root, String path, List<String> paths) {

        if (root != null) {
            path += Integer.toString(root.val);

            if (root.left == null && root.right == null) {
                paths.add(path);
            }

            path += "->";
            func(root.left, path, paths);
            func(root.right, path, paths);
        }
    }

129. Sum Root to Leaf Numbers

leetcode here

class Solution {

    int ans = 0;
    public int sumNumbers(TreeNode root) {
        func(root, 0);
        return ans;
    }

    void func(TreeNode root, int path) {

        if (root != null) {
            path = path*10 + root.val;

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

            func(root.left, path);
            func(root.right, path);
        }
    }
}

[Praactice] 112. Path Sum

leetcode here

class Solution {

    boolean hasPathSum = false;
    public boolean hasPathSum(TreeNode root, int targetSum) {
        
        func(root, targetSum);
        return hasPathSum;
    }

    void func(TreeNode root, int targetSum) {

        if (root != null && !hasPathSum) {

            if (root.left == null && root.right == null && root.val == targetSum) {
                hasPathSum = true;
            }

            func(root.left, targetSum - root.val);
            func(root.right, targetSum - root.val);
        }

    }
}