Trees Implementation

TreeNode Class (10 points)

Create a generic TreeNode.java class:

public class TreeNode<T> {
    public T data;
    public TreeNode<T> left;
    public TreeNode<T> right;
    
    public TreeNode(T data);
    public TreeNode(T data, TreeNode<T> left, TreeNode<T> right);
    
    public boolean isLeaf();            // No children
    public boolean hasLeft();           // Has left child
    public boolean hasRight();          // Has right child
    public int childCount();            // 0, 1, or 2
}

Binary Tree with Traversals (20 points)

Create a class BinaryTree.java:

public class BinaryTree<T> {
    protected TreeNode<T> root;
    
    public BinaryTree();
    public BinaryTree(TreeNode<T> root);
    
    // Traversals - return List<T>
    public List<T> preorder();          // Root → Left → Right
    public List<T> inorder();           // Left → Root → Right
    public List<T> postorder();         // Left → Right → Root
    public List<T> levelOrder();        // Level by level (BFS)
    
    // Iterative traversals (using stack/queue)
    public List<T> preorderIterative();
    public List<T> inorderIterative();
    public List<T> postorderIterative();
    
    // Tree properties
    public int height();                // Height of tree
    public int size();                  // Number of nodes
    public int countLeaves();           // Number of leaf nodes
    public boolean isEmpty();           // Is tree empty
}

// Example usage:
//       1
//      / \
//     2   3
//    / \
//   4   5
// preorder:  [1, 2, 4, 5, 3]
// inorder:   [4, 2, 5, 1, 3]
// postorder: [4, 5, 2, 3, 1]
// levelOrder: [1, 2, 3, 4, 5]

Binary Search Tree (25 points)

Create a class BinarySearchTree.java that extends BinaryTree:

public class BinarySearchTree<T extends Comparable<T>> extends BinaryTree<T> {
    
    // Core BST operations
    public void insert(T value);        // O(h) - insert value
    public boolean contains(T value);   // O(h) - search for value
    public void delete(T value);        // O(h) - delete value
    
    // BST-specific methods
    public T findMin();                 // Minimum value
    public T findMax();                 // Maximum value
    public T floor(T value);            // Largest ≤ value
    public T ceiling(T value);          // Smallest ≥ value
    public T successor(T value);        // Next larger element
    public T predecessor(T value);      // Previous smaller element
    
    // Range operations
    public List<T> rangeSearch(T low, T high);  // All values in [low, high]
    public int countInRange(T low, T high);     // Count in range
    
    // Validation
    public boolean isValidBST();        // Check BST property
}

Delete Cases:

• Leaf node: Simply remove the node
• One child: Replace with child
• Two children: Replace with inorder successor (or predecessor)

Tree Properties (15 points)

Determine various properties of a binary tree:

// P4a: Check if two trees are identical
public boolean isIdentical(TreeNode<Integer> t1, TreeNode<Integer> t2);

// P4b: Check if tree is symmetric (mirror of itself)
//     1
//    / \
//   2   2
//  / \ / \
// 3  4 4  3  → true
public boolean isSymmetric(TreeNode<Integer> root);

// P4c: Check if tree is balanced (height diff ≤ 1 at every node)
public boolean isBalanced(TreeNode<Integer> root);

// P4d: Check if tree is a complete binary tree
public boolean isComplete(TreeNode<Integer> root);

Path Problems (15 points)

Work with paths in binary trees:

// P5a: Find all root-to-leaf paths
//       1
//      / \
//     2   3
//    / \
//   4   5
// Returns: ["1->2->4", "1->2->5", "1->3"]
public List<String> rootToLeafPaths(TreeNode<Integer> root);

// P5b: Check if path with given sum exists (root to leaf)
public boolean hasPathSum(TreeNode<Integer> root, int targetSum);

// P5c: Find all paths with given sum
public List<List<Integer>> pathsWithSum(TreeNode<Integer> root, int targetSum);

// P5d: Maximum path sum (any path in tree)
// Path can start and end at any node
public int maxPathSum(TreeNode<Integer> root);

Lowest Common Ancestor (15 points)

Find LCA in different tree types:

// P6a: LCA in Binary Tree (nodes may not exist)
//       3
//      / \
//     5   1
//    / \ / \
//   6  2 0  8
//     / \
//    7   4
// LCA(5, 1) = 3, LCA(5, 4) = 5, LCA(6, 4) = 5
public TreeNode<Integer> lcaBinaryTree(TreeNode<Integer> root, int p, int q);

// P6b: LCA in Binary Search Tree (more efficient)
public TreeNode<Integer> lcaBST(TreeNode<Integer> root, int p, int q);

// P6c: Distance between two nodes
// distance(4, 6) = 4 (path: 4 → 2 → 5 → 6)
public int distanceBetweenNodes(TreeNode<Integer> root, int node1, int node2);

Tree Views (15 points)

Print different views of a tree:

//          1
//        /   \
//       2     3
//      / \   / \
//     4   5 6   7
//        / \
//       8   9

// P7a: Left view (first node at each level)
// [1, 2, 4, 8]
public List<Integer> leftView(TreeNode<Integer> root);

// P7b: Right view (last node at each level)
// [1, 3, 7, 9]
public List<Integer> rightView(TreeNode<Integer> root);

// P7c: Top view (looking from above)
// [4, 2, 1, 3, 7]
public List<Integer> topView(TreeNode<Integer> root);

// P7d: Bottom view (looking from below)
// [4, 8, 6, 9, 7]
public List<Integer> bottomView(TreeNode<Integer> root);

Tree Construction (20 points)

Build trees from traversals:

// P8a: Build tree from preorder and inorder traversals
// preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
//     3
//    / \
//   9  20
//     /  \
//    15   7
public TreeNode<Integer> buildFromPreorderInorder(int[] preorder, int[] inorder);

// P8b: Build tree from postorder and inorder traversals
public TreeNode<Integer> buildFromPostorderInorder(int[] postorder, int[] inorder);

// P8c: Build BST from preorder traversal
// preorder = [8,5,1,7,10,12]
public TreeNode<Integer> buildBSTFromPreorder(int[] preorder);

// P8d: Serialize and deserialize a binary tree
public String serialize(TreeNode<Integer> root);
public TreeNode<Integer> deserialize(String data);

Tree Modifications (15 points)

Modify tree structure:

// P9a: Invert/Mirror a binary tree
//     4              4
//    / \    →       / \
//   2   7          7   2
//  / \ / \        / \ / \
// 1  3 6  9      9  6 3  1
public TreeNode<Integer> invertTree(TreeNode<Integer> root);

// P9b: Flatten tree to linked list (preorder)
//     1              1
//    / \              \
//   2   5      →       2
//  / \   \              \
// 3   4   6              3
//                         \
//                          4 ...
public void flatten(TreeNode<Integer> root);

// P9c: Convert BST to sorted doubly linked list (in-place)
public TreeNode<Integer> bstToDoublyLinkedList(TreeNode<Integer> root);

Level-Order Problems (10 points)

Solve level-by-level problems:

// P10a: Zigzag level order traversal
// Level 0: left to right, Level 1: right to left, ...
//     3
//    / \
//   9  20
//     /  \
//    15   7
// Result: [[3], [20, 9], [15, 7]]
public List<List<Integer>> zigzagLevelOrder(TreeNode<Integer> root);

// P10b: Maximum width of tree (max nodes at any level, including nulls)
public int maxWidth(TreeNode<Integer> root);

// P10c: Vertical order traversal
// Group nodes by their horizontal distance from root
public List<List<Integer>> verticalOrder(TreeNode<Integer> root);

BST Operations (15 points)

Advanced BST problems:

// P11a: Kth smallest element in BST
public int kthSmallest(TreeNode<Integer> root, int k);

// P11b: Kth largest element in BST
public int kthLargest(TreeNode<Integer> root, int k);

// P11c: Convert sorted array to balanced BST
public TreeNode<Integer> sortedArrayToBST(int[] nums);

// P11d: Merge two BSTs into sorted list
public List<Integer> mergeTwoBSTs(TreeNode<Integer> root1, TreeNode<Integer> root2);

// P11e: Find pair with given sum in BST
public boolean findPairWithSum(TreeNode<Integer> root, int target);