Internship Assurance

DevOps & Cloud Engineering

A Binary tree, a nonlinear data structure, is a fundamental concept in computer science. In this article, we will delve into its practical application by using Java to find the lowest common ancestor in a Binary tree, a problem that often arises in real-world scenarios.

In a Binary tree, the lowest common ancestor is the lowest node in the tree that has both n1 and n2 as descendants of the same ancestor. We have to find the common ancestor of those descendants that shared the ancestor of n1 and n2 located farthest from the root. We will explore methods to find the LCA in a binary tree, discussing their time and space complexities.

Given a binary tree and two nodes, the task is to find their lowest Common Ancestor. Let’s consider the following binary tree, for example.

**Example**

**In this tree: **

** **

- The LCA of nodes 4 and 5 is 2
- The LCA of nodes 4 and 6 is 1.
- The LCA of nodes 7 and 8 is 5.

Let’s discuss the constraints of this problem

- 0 < n < 10 ^ 5, where n is the number of nodes.
- 0 < node.val < 10 ^ 9

One of the methods to find the Lowest Common Ancestor of two nodes in a binary tree is by storing the paths from the root to each of the two nodes and then comparing these paths to find the last common node. Because In any tree data structure, a unique path exists between any two nodes. Let’s see the algorithm of the Lowest Common Ancestor.

To find the lowest common ancestor of a binary tree, we will perform the following steps in our source code.

- We must store the path from the root to n1 in a list. Let it be path1.
- We must also store the path from the root to n2 in a list. Let it be path2.
- After getting both obtained paths, traverse the node path until the node path is common and return the node that occurs just before the mismatch.

Let’s see “how we can find the path from the root node to the target node”.

- We have to define the list of integers, such as the name of the list path. Then, pass it to a boolean-type recursive function, findPath, which accepts three arguments: root,val, and path.
- If the root is null, then return false.
- Push root.val in the path list.
- If our root.val is equal to val, then return true, as we’ve found that the desired node is any of the subtrees.
- We must remove the element at the last position in our path list.
- In the list, if nothing is worked out, then return false.

We will dry-run this approach using this given tree before implementing this algorithm in a programming language.

**Tree**

** **** **

**Find the Lowest Common Ancestor of (4,5)**

- Find the root node to the node with value 4. The first path will be

[1 -> 2 -> 4]

- Find the path from the root node to the node with value 5. path2

[1->2->5]

- Now, we will traverse both paths until we find the same path. Since we found a second mismatch, we will return the value just before the second index, which is 2.

**Find the Lowest Common Ancestor of (7,4)**

** **

- Find the path from the root node to the node with value 7. The first Path will be

[1->2->4->7]

- Find the path from the root node to the node with value 5. The second path will be

[1-> 2->4]

- Now, we must traverse both lists until the path is the same. Here, we will read the last index of path1, but if we do not find any mismatch, we will return the node at the last index of path1.

**Find the Lowest Common Ancestor of (5,8)**

** **

- Find the path from the root node to the node with value 5. The path will be

[1-> 2->4]

- Find the path from the root node to the node with value 8. The path will be

[1->3-> 7->8]

- Once again, we must traverse both path lists until the path has the same value. At the 1st index, we encounter a mismatch in paths, so we will return the node present at the 0th index 1.

**Output**

**Output**

**Output**

**Time Complexity: **In the worst case. We have to traverse the whole binary tree. It requires O(n) time to find the Lowest Common Ancestor.

**Space Complexity: **The overall space of the binary tree is O(h).

In the previous approach, we used traversing twice (once to find the path from the root node to the target node and from the root node to the 2nd target node. Now, we will optimise this approach so that it requires only one traversal to find the lowest ancestor of a binary tree with the lowest common ancestor.

Let’s look at the algorithm used to find the lowest common ancestor of a binary tree, as follows.

- For example, let’s define two boolean values, b1 and b2, which will help us verify whether both keys provided as the input exist in a binary tree.
- Then, a recursive function named find LowestCommontAncesstor is defined, and it accepts three arguments: node, n1, and n2.

- In this function, you must define the base condition that returns null whenever the node is null.
- Define a variable answer that initializes it to be null.
- You must check if the node’s value equals n1, make b1 true, and set the node to the answer.
- Otherwise, you have to check if node.value is equal to n2, make b2 true, and assign the node to answer.
- Recursive the left and right subtree and store their return values in the variables. We can define variables leftAnswer and righAnswer.
- If we find that the answer is no longer equal to null, then we will return it.
- Otherwise, If we find that both the leftAns and rightAns are not null, we will return the node.

- Both values b1 and b2 are true or not. If they both are true, we will return the node value returned by the recursive function. Otherwise, we will return -1.

**Output**

**Output**

**Output**

Let’s see the complexity of this approach.

**Time Complexity:**This approach’s Time Complexity will be O(n) to find the LCA of a binary tree. After traversing the whole binary tree in the worst case.**Space Complexity:**The height of the recursive tree can reach up to O(h), where h is the height of the binary tree. The overall space complexity of this algorithm is O(h).

Internship Assurance

DevOps & Cloud Engineering

In this approach, we will find the lowest common ancestor using the iterative approach. The main idea is to traverse the binary tree until we have found both of our target nodes, and then we will traverse back from the target node to the root using the Map data structure in this example. Let’s see the steps of this approach.

- Before moving forward, we must define the HashMap in which they store both keys and values.
- You also have to declare a queue of node type that will be used to traverse the in-level order fashion.
- Traverse in level order until we have found both our target nodes. While tracing, we will make sure that we map the nodes with their parents using the Map we declared initially.
- In the next step, we must move from the target1 to the root node and store the pat in a HashSet data structure.
- The first node is part of the part from target2 to the root node. This node is present in the HashSet in our answer

**Output**

**Output**

**Output**

Let’s describe the time and space complexity of the lowest common ancestor.

**Time Complexity**: In this approach, we must traverse the whole tee in the worst case, which costs O(n) time. The overall time complexity required to find the lowest common ancestor of a binary tree is O(n).**Space Complexity:**The space complexity of traversing a binary tree in a lever order fashion, the size queue can reach up to O(n). The overall space complexity is O(n).

This article taught us “how to find the lowest common ancestor in a Binary Tree.” We see various approaches to this problem. A common and efficient approach is one of the best approaches to solve this problem by recursive approach. By Understanding this approach, developers can make programs more efficient and useful. The recursive approach makes the program a balance of efficiency and simplicity, making the recursive approach a preferred choice for finding the lowest common Ancestor in binary trees.

FAQs

What is the Lowest Common Ancestor(LCA)?

The Lowest common ancestor of two nodes in the Binary tree is the deepest node, an ancestor of both nodes.

Can we find the Lowest Common Ancestor of more than two nodes?

Yes, Finding the Lowest Common Ancestor of more than two nodes can be extended from the binary case by iteratively applying the Lowest Common Ancestor function on pairs of nodes. This ensures the final result is the Lowest Common Ancestor of all the given nodes.

What is a Binary Tree?

A Binary tree is a hierarchical data structure in which each node has at most two children, referred to as the left and right child. It is a special case of a tree data structure in which every node has either 0, 1, or 2 children.

Can the LCA be found iteratively in a Binary Tree?

It can be found iteratively, but it is more complex than the recursive approach. The iterative approach involves using parent pointers to trace the paths from the nodes to the root and then finding the intersection of these paths.

Book a free counselling session

Get a personalized career roadmap

Get tailored program recommendations

Explore industry trends and job opportunities

Programs tailored for your success

Popular

Data Science

Technology

Finance

Management

Future Tech

Upskill with expert articles

View all

Hero Vired is a leading LearnTech company dedicated to offering cutting-edge programs in collaboration with top-tier global institutions. As part of the esteemed Hero Group, we are committed to revolutionizing the skill development landscape in India. Our programs, delivered by industry experts, are designed to empower professionals and students with the skills they need to thrive in today’s competitive job market.

Privacy policy and Terms of use

© 2024 Hero Vired. All rights reserved