Tree Based Common problems and patterns

 

Find the height of the tree.

public class BinaryTreeHeight { public static int heightOfBinaryTree(TreeNode root) { if (root == null) { return -1; // Height of an empty tree is -1 } int leftHeight = heightOfBinaryTree(root.left); int rightHeight = heightOfBinaryTree(root.right); // Height of the tree is the maximum of left and right subtree heights plus 1 for the root return Math.max(leftHeight, rightHeight) + 1; }

Find the Level of the Node.

private static int findLevel(TreeNode root, TreeNode node, int level) { if (root == null) { return -1; // Node not found, return -1 } if (root == node) { return level; // Node found, return current level } // Check left subtree int leftLevel = findLevel(root.left, node, level + 1); if (leftLevel != -1) { return leftLevel; // Node found in the left subtree } // Check right subtree int rightLevel = findLevel(root.right, node, level + 1); return rightLevel; // Node found in the right subtree (or not found at all) }

Search the node into Tree.

public class BinaryTreeSearch { public static TreeNode search(TreeNode root, int target) { if (root == null || root.value == target) { return root; } // Search in the left subtree TreeNode leftResult = search(root.left, target); if (leftResult != null) { return leftResult; // Node found in the left subtree } // Search in the right subtree TreeNode rightResult = search(root.right, target); return rightResult; // Node found in the right subtree (or not found at all) }

Find the level of the tree.

public static int treeLevel(TreeNode root) { if (root == null) { return 0; // Return 0 if the tree is empty } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int level = 0; while (!queue.isEmpty()) { int levelSize = queue.size(); // Number of nodes at the current level // Process all nodes at the current level for (int i = 0; i < levelSize; i++) { TreeNode current = queue.poll(); // Add left child to the queue if not null if (current.left != null) { queue.offer(current.left); } // Add right child to the queue if not null if (current.right != null) { queue.offer(current.right); } } level++; // Increment level after processing all nodes at the current level } return level - 1; // Subtract 1 to get the level index (root is at level 0) }

Level order traversal.

public class LevelOrderTraversal { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) return result; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int levelSize = queue.size(); List<Integer> currentLevel = new ArrayList<>(); for (int i = 0; i < levelSize; i++) { TreeNode currentNode = queue.poll(); currentLevel.add(currentNode.val); if (currentNode.left != null) queue.offer(currentNode.left); if (currentNode.right != null) queue.offer(currentNode.right); } result.add(currentLevel); } return result; }

Left view, right view top view, bottom view.

public List<Integer> leftView(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) return result; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int levelSize = queue.size(); for (int i = 0; i < levelSize; i++) { TreeNode current = queue.poll(); if (i == 0) { result.add(current.val); } if (current.left != null) queue.offer(current.left); if (current.right != null) queue.offer(current.right); } } return result; } // Right View public List<Integer> rightView(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) return result; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int levelSize = queue.size(); for (int i = 0; i < levelSize; i++) { TreeNode current = queue.poll(); if (i == levelSize - 1) { result.add(current.val); } if (current.left != null) queue.offer(current.left); if (current.right != null) queue.offer(current.right); } } return result; } // Top View public List<Integer> topView(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) return result; TreeMap<Integer, Integer> map = new TreeMap<>(); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int levelSize = queue.size(); for (int i = 0; i < levelSize; i++) { TreeNode current = queue.poll(); if (!map.containsKey(i)) { map.put(i, current.val); } if (current.left != null) queue.offer(current.left); if (current.right != null) queue.offer(current.right); } } for (int value : map.values()) { result.add(value); } return result; } // Bottom View public List<Integer> bottomView(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) return result; TreeMap<Integer, Integer> map = new TreeMap<>(); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int levelSize = queue.size(); for (int i = 0; i < levelSize; i++) { TreeNode current = queue.poll(); map.put(i, current.val); if (current.left != null) queue.offer(current.left); if (current.right != null) queue.offer(current.right); } } for (int value : map.values()) { result.add(value); } return result; }

Command ancestor.

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null || root == p || root == q) { return root; } TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); if (left != null && right != null) { return root; } return (left != null) ? left : right; }

Distance between two nodes in the tree.

public int distanceBetweenNodes(TreeNode root, TreeNode p, TreeNode q) { TreeNode lca = lowestCommonAncestor(root, p, q); int distanceP = findDistanceFromNode(lca, p, 0); int distanceQ = findDistanceFromNode(lca, q, 0); return distanceP + distanceQ; } private int findDistanceFromNode(TreeNode source, TreeNode target, int distance) { if (source == null) { return -1; } if (source.val == target.val) { return distance; } int leftDistance = findDistanceFromNode(source.left, target, distance + 1); int rightDistance = findDistanceFromNode(source.right, target, distance + 1); return Math.max(leftDistance, rightDistance); }

IS BST

boolean isBST()

    {

        return isBSTUtil(root, Integer.MIN_VALUE,

                         Integer.MAX_VALUE);

    }

 

    /* Returns true if the given tree is a BST and its

      values are >= min and <= max. */

    boolean isBSTUtil(Node node, int min, int max)

    {

        /* an empty tree is BST */

        if (node == null)

            return true;

 

        /* false if this node violates the min/max

         * constraints */

        if (node.data < min || node.data > max)

            return false;

 

        /* otherwise check the subtrees recursively

        tightening the min/max constraints */

        // Allow only distinct values

        return (

            isBSTUtil(node.left, min, node.data - 1)

            && isBSTUtil(node.right, node.data + 1, max));

    }