.png)
We recommend you to go through Trees - I first before reviewing this article.
LCA in Binary Tree
The LCA or Lowest Common Ancestor of any two nodes N1 and N2 is defined as the common ancestor of both the nodes which is closest to them. That's the distance of the common ancestor from the nodes N1 and N2 should be least possible.
Below represents a tree and LCA of different pair of nodes (N1, N2) in it:
10
/ \
20 30
/ \ / \
40 50 60 70
Examples:
LCA(40, 50) = 20
LCA(40, 60) = 10
LCA(30, 40) = 10
LCA(20, 40) = 20 Method 1:
We can observe that the LCA of the given nodes will be the last common node in the paths from the root node to the given nodes.
For Example, Consider the above-given tree and nodes 4 and 5.
The path from the root to node 40: [10, 20, 40].
The path from the root to node 50: [10, 20, 50].
The last common node is 20 which will be the LCA.
Algorithm:
Find the path from the root node to node n1 and store it in a vector or array.
Find the path from the root node to node n2 and store it in another vector or array.
Traverse both paths until the values in arrays are the same. Return the common element just before the mismatch.
C++ Program for Lowest Common Ancestor in a Binary Tree:
#include <iostream>
#include <vector>
using namespace std;
struct Node {
int key;
struct Node *left, *right;
};
Node* newNode(int k)
{
Node* temp = new Node;
temp->key = k;
temp->left = temp->right = NULL;
return temp;
}
// returns true if path exists otherwise false
bool findPath(Node* root, vector<int>& path, int k)
{
// base case
if (root == NULL)
return false;
// The node will be removed if
// not in path from root to k
path.push_back(root->key);
if (root->key == k)
return true;
// Check if k is in left or right sub-tree
if ((root->left && findPath(root->left, path, k)) ||
(root->right && findPath(root->right, path, k)))
return true;
// If not present in subtree rooted with root,
// remove root from path[] and return false
path.pop_back();
return false;
}
// Function to return LCA if node n1, n2 are
// present in the given binary tree, otherwise
// return -1
int findLCA(Node* root, int n1, int n2)
{
// to store paths
vector<int> path1, path2;
// Find paths from root to n1 and root to n1.
// If either n1 or n2 is not present, return -1
if (!findPath(root, path1, n1) || !findPath(root, path2, n2))
return -1;
int i;
for (i = 0; i < path1.size() && i < path2.size(); i++)
if (path1[i] != path2[i])
break;
return path1[i - 1];
}
int main()
{
Node* root = newNode(10);
root->left = newNode(20);
root->right = newNode(30);
root->left->left = newNode(40);
root->left->right = newNode(50);
root->right->left = newNode(60);
root->right->right = newNode(70);
cout << "LCA(40, 50) = " << findLCA(root, 40, 50);
cout << "\nLCA(40, 60) = " << findLCA(root, 40, 60);
cout << "\nLCA(30, 40) = " << findLCA(root, 30, 40);
cout << "\nLCA(20, 40) = " << findLCA(root, 20, 40);
return 0;
}Output:
LCA(40, 50) = 20
LCA(40, 60) = 10
LCA(30, 40) = 10
LCA(20, 40) = 20Time Complexity: O(N)
Space Complexity: O(N)
Method 2:
The method 1 finds LCA in O(N) time but requires three tree traversals plus extra spaces for path arrays. If we assume that the keys are present in Binary Tree, we will find LCA using a single traversal of Binary Tree and without extra storage for path arrays.
The idea is to traverse the tree starting from the root node. If any of the given keys (n1 and n2) matches with root, then the root is LCA. If the root doesn't match with any of the keys, we recur for left and right subtrees. The node which has one key present in its left subtree and therefore the other key present within the right subtree is that the LCA. If both keys lie in the left subtree, then the left subtree has LCA also, otherwise, LCA lies within the right subtree.
C++ Program to find LCA of n1 and n2 using one traversal of Binary Tree
#include <iostream>
using namespace std;
struct Node {
struct Node *left, *right;
int key;
};
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return temp;
}
struct Node* findLCA(struct Node* root, int n1, int n2)
{
if (root == NULL)
return NULL;
if (root->key == n1 || root->key == n2)
return root;
Node* left_lca = findLCA(root->left, n1, n2);
Node* right_lca = findLCA(root->right, n1, n2);
if (left_lca && right_lca)
return root;
return (left_lca != NULL) ? left_lca : right_lca;
}
int main()
{
Node* root = newNode(10);
root->left = newNode(20);
root->right = newNode(30);
root->left->left = newNode(40);
root->left->right = newNode(50);
root->right->left = newNode(60);
root->right->right = newNode(70);
cout << "LCA(40, 50) = " << findLCA(root, 40, 50)->key;
cout << "\nLCA(40, 60) = " << findLCA(root, 40, 60)->key;
cout << "\nLCA(30, 40) = " << findLCA(root, 30, 40)->key;
cout << "\nLCA(20, 40) = " << findLCA(root, 20, 40)->key;
return 0;
}Output:
LCA(40, 50) = 20
LCA(40, 60) = 10
LCA(30, 40) = 10
LCA(20, 40) = 20Width of a Binary Tree
The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two end nodes.
The diagram below shows two trees each with diameter seven, the leaves that form the ends of the longest path are shaded.
1st)
1
/ \
2 3
/ \ \
4 5 6
/ \ \
7 (8) (9)
Diameter 7 nodes through root
2nd)
1
/ \
2 3
/ \
4 5
/ \ \
6 7 8
/ / \
(9) 10 (11)
Diameter 7 nodes not thorugh root Solution: The diameter of a tree T is the largest of the following quantities:
The diameter of T's right subtree.
The diameter of T's left subtree.
The longest path between leaves that goes through the root of T.
The longest path between leaves that goes through a particular node say, nde can be calculated as:
1 + height of left subtree of nde + height of right subtree of nde
Therefore, final Diameter of a node can be calculated as:
Diameter = maximum(lDiameter, rDiameter, 1 + lHeight + rHeight) Where, lDiameter = Diameter of left subtree rDiameter = Diameter of right subtree lHeight = Height of left subtree rHeight = Height of right subtree
C++ program to calculate Diameter of a Binary Tree:
#include <bits/stdc++.h>
using namespace std;
struct node
{
int data;
struct node* left, *right;
};
struct node* newNode(int data);
int height(struct node* node);
int diameter(struct node * tree)
{
if (tree == NULL)
return 0;
int lheight = height(tree->left);
int rheight = height(tree->right);
int ldiameter = diameter(tree->left);
int rdiameter = diameter(tree->right);
return max(lheight + rheight + 1, max(ldiameter, rdiameter));
}
int height(struct node* node)
{
if(node == NULL)
return 0;
return 1 + max(height(node->left), height(node->right));
}
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
int main()
{
struct node *root = newNode(10);
root->left = newNode(20);
root->right = newNode(30);
root->left->left = newNode(40);
root->left->right = newNode(50);
cout<<"Diameter: "<<diameter(root);
return 0;
}Output:
Diameter: 4Time Complexity: O(N^2), where N is the number of nodes in the binary tree.
Views of a Binary Tree
Here the task is to print the nodes of the binary tree when viewed from different sides.
Example:
Consider the Below Binary Tree:
10
/ \
20 30
/ \ / \
40 50 60 70
Left View: 10, 20, 40
Right View: 10, 30, 70
Top View: 40, 20, 10, 30, 70
Bottom View: 40, 50, 60, 70Left View: Nodes view appearing in the of the tree are the first nodes at every level. So we will do level order traversal using a marker to identify levels and print the first node at every level.
Function to print the left view of the binary tree:
void leftViewUtil(Node root)
{
//queue for Level order Traversal
queue<Node*> q;
if (root == NULL)
return;
q.push(root);
q.push(NULL);
while (!q.empty()) {
Node* temp = q.front();
if (temp) {
print temp->data;
while (q.front() != NULL) {
if (temp->left)
q.push(temp->left);
if (temp->right)
q.push(temp->right);
q.pop();
temp = q.front();
}
q.push(NULL);
}
q.pop();
}
} Right View: Printing Right View of the Binary Tree is similar to the above approach of printing the Left view of the tree.
The idea is to print the last node present at every level. So, perform a level order traversal using a delimiter to identify levels and print the last node present at every level.
Top View: Top view of a binary tree is the set of nodes visible when the tree is viewed from the top.
A node x is there in output if x is the topmost node at its horizontal distance. The horizontal distance of the left child of a node x is equal to the horizontal distance of x minus 1, and that of the right child is the horizontal distance of x plus 1.
So, the idea is to do a level order traversal of the tree and calculate the horizontal distance of every node from the root node and print those nodes which are the first nodes of a particular horizontal distance.
Below function implements the above approach:
//hd is horizontal distance
struct Node
{
Node * left;
Node* right;
int hd;
int data;
};
void topview(Node* root)
{
if(root==NULL)
return;
queue<Node*>q;
map<int,int> m;
int hd=0;
root->hd = hd;
q.push(root);
print "The top view of the tree is : ";
while(q.size())
{
hd = root->hd;
if(m.count(hd)==0)
m[hd]=root->data;
if(root->left)
{
root->left->hd=hd-1;
q.push(root->left);
}
if(root->right)
{
root->right->hd=hd+1;
q.push(root->right);
}
q.pop();
root=q.front();
}
for(auto i=m.begin();i!=m.end();i++)
{
cout<<i->second<<" ";
}
} Bottom View: The Bottom View of a binary tree can be printed using a similar approach as that of printing the Top View.
A node x is there in output if x is the bottom-most instead of the topmost node at its horizontal distance. The process of printing the bottom view is almost the same as that of top view with a little modification that while storing the node's data along with a particular horizontal distance in the map, keep updating the node's data in the map for a particular horizontal distance so that the map contains the last node appearing with a particular horizontal distance instead of first.
Happy Coding!
Follow us on Instagram @programmersdoor
Join us on Telegram @programmersdoor
Please write comments if you find any bug in the above code/algorithm, or find other ways to solve the same problem.
Follow Programmers Door for more.
Comments