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

Post a Comment

Popular posts from this blog

Learning How to Map One-to-Many Relationships in JPA Spring Boot with PostgreSQL

  Introduction In this blog post, we explore how to effectively map one-to-many relationships using Spring Boot and PostgreSQL. This relationship type is common in database design, where one entity (e.g., a post) can have multiple related entities (e.g., comments). We'll dive into the implementation details with code snippets and provide insights into best practices. Understanding One-to-Many Relationships A one-to-many relationship signifies that one entity instance can be associated with multiple instances of another entity. In our case: Post Entity : Represents a blog post with fields such as id , title , content , and a collection of comments . Comment Entity : Represents comments on posts, including fields like id , content , and a reference to the post it belongs to. Mapping with Spring Boot and PostgreSQL Let's examine how we define and manage this relationship in our Spring Boot application: Post Entity  @Entity @Getter @Setter @Builder @AllArgsConstructor @NoArgsCon...
Post a Comment
Read more

Understanding the Advertisement Domain: A Comprehensive Overview Part 2

 The advertisement domain is a complex and dynamic ecosystem that involves various technologies and platforms working together to deliver ads to users in a targeted and efficient manner. The primary goal is to connect advertisers with their target audience, increasing brand visibility, user engagement, and revenue generation. In this blog, we will delve into the different components of the advertisement ecosystem, key concepts like programmatic advertising and real-time bidding (RTB), and provide a practical example to illustrate how it all works. Key Components of the Advertisement Domain The advertisement domain broadly consists of the following components: Advertisers : These are brands or companies that want to promote their products or services through advertisements. They set up ad campaigns targeting specific user segments. Publishers : These are websites, mobile apps, or digital platforms that display ads to users. Publishers monetize their content by selling ad space to ad...
Post a Comment
Read more