Skip to main content

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));
    }





Comments

Popular posts from this blog

Stay Updated As Software Engineer

Are you a software engineer looking to stay updated and grow in your field? We've got you covered with over 50 valuable resources to keep you on the cutting edge of technology. From newsletters to books, we've curated a diverse list just for you.   Newsletters:   Pragmatic Engineer: Link   TLDR: Link   Level-up software engineering: Link   Coding challenges: Link   Engineers Codex: Link   Techlead Mentor: Link   Saiyan Growth letter: Link   Wes Kao: Link   Addy Osmani: Link   And many more (see link below)   Books:   Engineering:   A Philosophy of Software Design Link   Clean Code Link   Communication & Soft Skills:   Smart Brevity Link   Connect: Building Exceptional Relationships Link   Crucial Conversations Link   Engineers Survival Guide Link   Leadership:   The Manager's Path Link   Staff Engineer: Leadership Beyond the Management Track Link   The Coaching Habit: Say Less, Ask More Link   While we can't list all 50+ resources here, this is a fantastic sta

12 Must-Know LeetCode+ Links for Coding Excellence

Introduction: Welcome to a comprehensive guide on mastering essential coding techniques and strategies! Whether you're a beginner or an experienced coder, these LeetCode+ links will elevate your skills and make you a more proficient problem solver. Let's dive into the world of algorithms, data structures, and coding patterns that will empower you to tackle complex challenges with confidence. 1. Sliding Window Learn the art of efficient sliding window techniques: Sliding Window - Part 1 and Sliding Window - Part 2 . Enhance your coding prowess and optimize algorithms with these invaluable insights. 2. Backtracking Unlock the power of backtracking algorithms: Backtracking . Discover how to systematically explore possibilities and find optimal solutions to a variety of problems. 3. Greedy Algorithm Master the art of making locally optimal choices for a globally optimal solution: Greedy Algorithm . Dive into strategies that prioritize immediate gains and lead to optimal outcomes