Trees

The problem involves counting islands in a 2D grid of ‘1’s (land) and ‘0’s (water). An efficient way to do this is by using Depth-First Search (DFS) to mark visited land as ‘0’. Two approaches are discussed: a brute-force method tracking visited cells and an optimized method that modifies the grid to reduce space complexity.

You are provided with a binary tree, return the length of the diameter. The diameter of the binary tree is defined as the length of the longest path between any two nodes in the tree. In the above example the diameter of the binary tree is 7. Problem Statement: We can easily find out the distance between two nodes in a binary tree. In the given example, the distance between node 5 and 8 is 4. The distance between node 2 and 6 is 3, the distance between node 8 …

Question: Given the root pointer to a binary tree, find the left view of the tree. Input: Sample Tree (Pointer to node 1 is given). Output: 1, 2, 4 At a single glance of the problem, we can understand that we need to perform a level order traversal on the tree. This is similar to finding the number of levels in a tree. At the start of each level, we just print the first element. This can be done with the algorithm below:- Time Complexity:- O(n) Space Complexity:- O(n) Ideone …

Question: How many binary trees are possible with n nodes? Input: Nodes = 3 Output: Answer = 5 For, example consider a tree with 3 nodes (n = 3), it will have a maximum combination of 5 different trees In general, if there are n nodes, there exist (2n)!/(n+1)! different trees.

Question: Given the root pointer to a binary tree, find the LCA (Least Common Ancestor) of two nodes in the tree. Input: Sample Tree (Pointer to node 1 is given). Find LCA of node 5 and 4 Output: Answer = 3 A simple recursive approach can be used to find the LCA (Least common ancestor).

Question: Given 2 binary trees, determine if they are mirror of each other Input: 2 tree pointers are given. (Root pointer) Output: TRUE We can again apply the recursive sub-structure property of the tree here. The algorithm can be implemented as:- Time Complexity:- O(n) Space Complexity:- O(n) due to a recursive stack

Question: Given the root pointer to a binary tree, find the sum of all its elements without using recursion. Input: Sample Tree (Pointer to node 1 is given). Output: Sum = 15 We discussed how to find the sum of all elements of a binary tree using recursion in this post. Given a binary tree, find the sum of all elements. If recursion seems tough to you , you can always go by the iterative approach and use Level Order Traversal of binary tree. While performing a level order traversal, …

Question: Given the root pointer to a binary tree, find the sum of all its elements. Input: Sample Tree (Pointer to node 1 is given). Output: Sum = 15 This is a very simple problem. Since the tree follows a recursive sub-structure, we can recursively call left tree sum, right tree sum and then add their values to the current node data.

Question: Given a binary tree, find its mirror tree. Input: A tree pointer is given. (Root pointer) Output: Pointer of mirrored tree. We can easily get the mirrored tree by a simple recursive algorithm. We traverse the tree and swap the left and right pointers. Time Complexity:- O(n) Space Complexity:- O(n) (due to recursive stack)

Question: Given two binary trees, find if they are structurally identical. Input: 2 trees are given. (Root pointers) Output: TRUE When we say structurally identical trees, we mean that both the trees have exactly the same number of nodes, arranged in the exactly same way. It is not necessary that the value of each node should also be the same. Since, we need to traverse each node of the tree and each node has the same property of having a data value, a left child and a right child, we …