Problems

Binary Tree

Diameter of Binary Tree

Problem Statement: Find the diameter of a binary tree

Approach:

The diameter of a binary tree is the length of the longest path between any two nodes in the tree. This path may or may not pass through the root.

int diameter(Node root) {
    if (root == null) return 0;
    int leftHeight = height(root.left);
    int rightHeight = height(root.right);
    int leftDiameter = diameter(root.left);
    int rightDiameter = diameter(root.right);
    return Math.max(leftHeight + rightHeight + 1, Math.max(leftDiameter, rightDiameter));
}
int height(Node node) {
    if (node == null) return 0;
    return 1 + Math.max(height(node.left), height(node.right));
}

---

Maximum sum level

Problem Statement: Find the level in a binary tree that has maximum sum.

Approach:
Same as finding num of levels but keep track of the level sum.

int maxLevelSum(Node root) {
    if (root == null) return 0;
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);
    int maxSum = Integer.MIN_VALUE;

    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        int levelSum = 0;

        for (int i = 0; i < levelSize; i++) {
            Node node = queue.poll();
            levelSum += node.data;

            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        maxSum = Math.max(maxSum, levelSum);
    }
    return maxSum;
}

---

LCA of 2 nodes

Problem Statement: Find the lowest common ancestor of two nodes in a binary tree

Approach:
The LCA of two nodes in a binary tree is the deepest node that is an ancestor of both nodes.

Node lca(Node root, int n1, int n2) {
    if (root == null) return null;
    if (root.data == n1 || root.data == n2) return root;

    Node leftLCA = lca(root.left, n1, n2);
    Node rightLCA = lca(root.right, n1, n2);

    if (leftLCA != null && rightLCA != null) {
        return root; // This is the LCA
    }
    return (leftLCA != null) ? leftLCA : rightLCA; // Return non-null child
}

---

Construct BT from Inorder and Preorder

Problem Statement: Given an inorder traversal and preorder traversal of a binary tree. Build the binary tree from them.

Approach:
LDR + DLR The first element in the preorder traversal is the root. Find this root in the inorder traversal to determine the left and right subtrees. Repeat this process recursively for the left and right subtrees.

Node buildTree(int[] inorder, int[] preorder, int inStart, int inEnd, int preStart, int preEnd) {
    if (inStart > inEnd || preStart > preEnd) return null;

    Node root = new Node(preorder[preStart]);
    int inIndex = findIndex(inorder, inStart, inEnd, root.data);

    root.left = buildTree(inorder, preorder, inStart, inIndex - 1, preStart + 1, preStart + (inIndex - inStart));
    root.right = buildTree(inorder, preorder, inIndex + 1, inEnd, preStart + (inIndex - inStart) + 1, preEnd);

    return root;
}

---

Given 2 traversal, can we construct unique BT?

To build a unique BT we need inorder and any one of the other traversals (preorder, level order or postorder).

---

Zigzag Level Order Traversal

Problem Statement: Print the zigzag level order traversal of a binary tree.

Approach:
Maintain 2 stacks and a boolean to track the direction of traversal.
If the boolean is true, pop from the first stack and push children to the second stack in left-to-right order.
If false, do the opposite.

void zigzagLevelOrder(Node root) {
    if (root == null) return;

    Stack<Node> currentLevel = new Stack<>();
    Stack<Node> nextLevel = new Stack<>();
    boolean leftToRight = true;

    currentLevel.push(root);

    while (!currentLevel.isEmpty()) {
        Node node = currentLevel.pop();
        System.out.print(node.data + " ");

        if (leftToRight) {
            if (node.left != null) nextLevel.push(node.left);
            if (node.right != null) nextLevel.push(node.right);
        } else {
            if (node.right != null) nextLevel.push(node.right);
            if (node.left != null) nextLevel.push(node.left);
        }

        if (currentLevel.isEmpty()) {
            leftToRight = !leftToRight;
            Stack<Node> temp = currentLevel;
            currentLevel = nextLevel;
            nextLevel = temp;
        }
    }
    System.out.println();
}

---

Maximum Path Sum

Problem Statement:

Approach:
At each node find max(left_max_sum, right_max_sum, left_h_sum + node + right_h_sum)

Refer Problem 124

---

Serialize and Deserialize BT

Problem Statement: Design an algorithm to serialize and deserialize a binary tree.

Approach:

Refer Problem 297

---

Binary Search Tree

Number of BSTs possible with n nodes

Refer DP Problem

---

Check if a BT is BST

Problem Statement: Give a binary tree, return true if its a bst else false

Approach:

• Inorder traversal has ascending order
• Find the max value in left subtree is less than node data and min value in right subtree is greater than node data.

fun isBST(root: TreeNode): Boolean {
//    if(root == null) return true;
//    if(!isBST(root->left, prev))
//        return false;
//    if(root.data < prev)
//        return false;
//    return isBST(root->right, root.data);

    val stack = LinkedList<TreeNode>()

    var node = root
    var prev = Int.MIN_VALUE
    while(node != null && stack.isNotEmpty()) {
        while(node) {
            stack.add(node)
            node = node.left
        }
        node = stack.removeLast()
        if(node.data > prev) return false
        node = node.right
    }
    return true
}

---

Given sorted linked list, construct balanced BST

Problem Statement:

Approach:

---

kth smallest

Problem Statement: Given a binary search tree, find the kth smallest element.

Approach: Inorder traversal & keep track of the count of processed nodes.

---

Predecessor and successor

Problem Statement:

Approach:

---

AVL Trees

Check if a BST is an AVL tree

Problem Statement: Given a bst, return true if it's an AVL tree else false

Approach:

fun isAVL(root: AVLNode?): Boolean {
    if (root == null) return true
    return checkHeight(root) != -1
}

fun checkHeight(root: AVLNode?): int {
    if(root == null) return 0
    val lh = checkHeight(root.left)
    val rh = checkHeight(root.right)

    if(lh == -1 || rh == -1 || abs(rh - lh) > 1) return -1
    return 1 + max(lh, rh)
}