Tree algo Flashcards
applications of Trees:
To represent hierarchical data.
Binary Search Trees.
Binary heap
B and B+ Trees in DBMS
Spanning and Shortest path in computer networks
Parse Tree and Expression Tree in Compilers.
implementation to represent a Binary Tree.
In Binary Tree every node has at most two children.
#include (bits/stdc++.h>
using namespace std;
struct Node
{
int key;
struct Node *left;
struct Node *right;
Node(int k){
key=k;
left=right=NULL;
}
};
int main() {
Node *root=new Node(10); root->left=new Node(20); root->right=new Node(30); root->left->left=new Node(40); }
Implementation of Inorder Traversal
#include (bits/stdc++.h> using namespace std;
struct Node
{
int key;
struct Node *left;
struct Node *right;
Node(int k){
key=k;
left=right=NULL;
}
};
void inorder(Node *root){
if(root!=NULL){
inorder(root->left);
cout((root->key((" ";
inorder(root->right);
}
}
int main() {
Node *root=new Node(10); root->left=new Node(20); root->right=new Node(30); root->right->left=new Node(40); root->right->right=new Node(50);
inorder(root); } 20 10 40 30 50
Implementation of Preorder Traversal
#include (bits/stdc++.h> using namespace std;
struct Node
{
int key;
struct Node *left;
struct Node *right;
Node(int k){
key=k;
left=right=NULL;
}
};
void preorder(Node *root){
if(root!=NULL){
cout((root->key((" ";
preorder(root->left);
preorder(root->right);
}
}
int main() {
Node *root=new Node(10); root->left=new Node(20); root->right=new Node(30); root->right->left=new Node(40); root->right->right=new Node(50);
preorder(root); } 10 20 30 40 50
Implementation of Postorder Traversal
#include (bits/stdc++.h> using namespace std;
struct Node
{
int key;
struct Node *left;
struct Node *right;
Node(int k){
key=k;
left=right=NULL;
}
};
void postorder(Node *root){
if(root!=NULL){
postorder(root->left);
postorder(root->right);
cout((root->key((" ";
}
}
int main() {
Node *root=new Node(10); root->left=new Node(20); root->right=new Node(30); root->right->left=new Node(40); root->right->right=new Node(50);
postorder(root); } 20 40 50 30 10
Implementation of function to calculate Height of Binary Tree
Height of Binary Tree is the number of nodes between the longest path from root to leaf node(including the root and leaf node).
#include (bits/stdc++.h> using namespace std;
struct Node
{
int key;
struct Node *left;
struct Node *right;
Node(int k){
key=k;
left=right=NULL;
}
};
int height(Node *root){
if(root==NULL)
return 0;
else
return (1+max(height(root->left),height(root->right)));
}
int main() {
Node *root=new Node(10); root->left=new Node(20); root->right=new Node(30); root->right->left=new Node(40); root->right->right=new Node(50);
cout((height(root); } output 3
Print nodes at k distance in a tree
Nodes at distance k from the root are basically the nodes at (k+1)th level of the Binary Tree.
#include (bits/stdc++.h> using namespace std;
struct Node
{
int key;
struct Node *left;
struct Node *right;
Node(int k){
key=k;
left=right=NULL;
}
};
void printKDist(Node *root,int k){
if(root==NULL)return;
if(k==0){cout((root->key((" ";}
else{
printKDist(root->left,k-1);
printKDist(root->right,k-1);
}
}
int main() {
Node *root=new Node(10); root->left=new Node(20); root->right=new Node(30); root->left->left=new Node(40); root->left->right=new Node(50); root->right->right=new Node(70); root->right->right->right=new Node(80); int k=2;
printKDist(root,k); } 40 50 70
Implement level order traversal for a binary tree
Level order traversal of a tree is breadth first traversal of binary tree
#include (bits/stdc++.h> using namespace std;
struct Node
{
int key;
struct Node *left;
struct Node *right;
Node(int k){
key=k;
left=right=NULL;
}
};
void printLevel(Node *root){
if(root==NULL)return;
queue(Node *>q;
q.push(root);
while(q.empty()==false){
Node *curr=q.front();
q.pop();
cout((curr->key((" ";
if(curr->left!=NULL)
q.push(curr->left);
if(curr->right!=NULL)
q.push(curr->right);
}
}
int main() {
Node *root=new Node(10); root->left=new Node(20); root->right=new Node(30); root->left->left=new Node(40); root->left->right=new Node(50); root->right->left=new Node(60); root->right->right=new Node(70);
printLevel(root); } 10 20 30 40 50 60 70
Calculate size of binary tree
Size of Binary Tree is the total numbers of nodes present in that Tree.
#include (bits/stdc++.h> using namespace std;
struct Node
{
int key;
struct Node *left;
struct Node *right;
Node(int k){
key=k;
left=right=NULL;
}
};
int getSize(Node *root){
if(root==NULL)
return 0;
else
return 1+getSize(root->left)+getSize(root->right);
}
int main() {
Node *root=new Node(10); root->left=new Node(20); root->right=new Node(30); root->left->left=new Node(40); root->left->right=new Node(50); root->right->right=new Node(60);
cout((getSize(root); } 6
Maximum node in a tree
#include (bits/stdc++.h> using namespace std;
struct Node
{
int key;
struct Node *left;
struct Node *right;
Node(int k){
key=k;
left=right=NULL;
}
};
int getMax(Node *root){
if(root==NULL)
return INT_MIN;
else
return max(root->key,max(getMax(root->left),getMax(root->right)));
}
int main() {
Node *root=new Node(20); root->left=new Node(80); root->right=new Node(30); root->right->left=new Node(40); root->right->right=new Node(50);
cout((getMax(root); } 80
Iterative Inorder traversal
TC = theta(n)
SC - O(h)
Iterative Preorder Traversal (Simple)
A O(n) extra space and O(n) time solution
Iterative Preorder Traversal (Space Optimized)
O(h) extra space and O(n) time solution
Children Sum Parent
Given a Binary Tree. Check whether all of its nodes have the value equal to the sum of their child nodes.
Example 1:
Input:
10
/
10
Output: 1
Explanation: Here, every node is sum of
its left and right child.
Example 2:
Input:
1
/ \
4 3
/ \
5 N
Output: 0
Explanation: Here, 1 is the root node
and 4, 3 are its child nodes. 4 + 3 =
7 which is not equal to the value of
root node. Hence, this tree does not
satisfy the given conditions.
Your Task:
You don’t need to read input or print anything. Your task is to complete the function isSumProperty() that takes the root Node of the Binary Tree as input and returns 1 if all the nodes in the tree satisfy the following properties. Else, it returns 0.
For every node, data value must be equal to the sum of data values in left and right children. Consider data value as 0 for NULL child. Also, leaves are considered to follow the property.
Expected Time Complexiy: O(N).
Expected Auxiliary Space: O(Height of the Tree).
Algorithm:
For each node, if node is null or both child nodes are null, return true.
Else if left and right child are not null then store their value.
If sum of stored data of left and right child is equal to the current node data and recursively for the left and right subtree, parent data is equal to sum of child data then return true else return false.
int isSumProperty(struct Node *node)
{
int left_data = 0, right_data = 0;
//if node is null or both child nodes are null, we return true.
if (node == NULL ||(node->left == NULL && node->right == NULL))
return 1;
else {
//if left child is not null then we store its value.
if (node->left != NULL)
left_data = node->left->data;
//if right child is not null then we store its value.
if (node->right != NULL)
right_data = node->right->data;
//if sum of stored data of left and right child is equal to the current
//node data and recursively for the left and right subtree, parent data
//is equal to sum of child data then we return true.
if ((node->data == left_data + right_data) &&
isSumProperty(node->left) &&
isSumProperty(node->right))
return 1;
//else we return false.
else
return 0;
}
Determine if Two Trees are Identical
Given two binary trees, the task is to find if both of them are identical or not.
Example 2:
Input:
1 1
/ \ / \
2 3 2 3
Output: Yes
Explanation: There are two trees both
having 3 nodes and 2 edges, both trees
are identical having the root as 1,
left child of 1 is 2 and right child
of 1 is 3.
Example 2:
Input:
1 1
/ \ / \
2 3 3 2
Output: No
Explanation: There are two trees both
having 3 nodes and 2 edges, but both
trees are not identical.
Your task:
Since this is a functional problem you don’t have to worry about input, you just have to complete the function isIdentical() that takes two roots as parameters and returns true or false. The printing is done by the driver code.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the Tree).
Two trees are identical when they have same data and arrangement of data is also same. To identify if two trees are identical, we need to traverse both trees simultaneously, and while traversing we need to compare data and children of the trees.
Algorithm:
1. If both nodes are empty then return 1.
2. Else If both nodes are non-empty
(a) Check data of the root nodes (tree1->data == tree2->data)
(b) Check left subtrees recursively.
(c) Check right subtrees recursively.
(d) If a,b and c are true then return 1.
3 Else return 0 (one is empty and other is not).
class Solution
{
public:
//Function to check if two trees are identical.
bool isIdentical(Node* a, Node* b)
{
//if both nodes are null then we return true.
if (a == NULL && b == NULL)
return true;
if (a != NULL && b != NULL)
{
//we check if data at both nodes and left and right subtree of
//both the nodes are equal then we return true else return false.
return
(
a->data == b->data &&
isIdentical(a->left, b->left) &&
isIdentical(a->right, b->right)
);
}
//returning false if one of the nodes is null and other isn't.
return false;
}
};
Vertical Width of a Binary Tree
Given a Binary Tree of N nodes. Find the vertical width of the tree.
Example 1:
Input:
1
/ \
2 3
/ \ / \
4 5 6 7
\ \
8 9
Output: 6
Explanation: The width of a binary tree is
the number of vertical paths in that tree.
Example 2:
Input:
1
/ \
2 3
Output: 3
Your Task:
You don’t have to read input or print anything. Your task is to complete the function verticalWidth() which takes root as the only parameter, and returns the vertical width of the binary tree.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the Tree).
Maintain 3 variables maximum and minimum, and curr.
Maximum and Minimum will store the max value of width of tree and min value of width of tree, over all recursion calls.
- Pass Maximum and Minimum through reference for updation.
- For call on left subree pass curr-1 and for call on right subree pass curr + 1
After all the calls have been made, return the sum of maximum and absolute value of minimum+1.
void lengthUtil(Node* root, int &maximum, int &minimum, int curr)
{
//base case for recursion.
if (root == NULL)return;
//calling the lengthUtil function recursively for the left subtrees. lengthUtil(root->left, maximum, minimum, curr - 1);
//updating maximum and minimum. if (minimum > curr)minimum = curr; if (maximum ( curr)maximum = curr;
//calling the lengthUtil function recursively for the right subtrees. lengthUtil(root->right, maximum, minimum, curr + 1); }
//Function to find the vertical width of a Binary Tree.
int verticalWidth(Node* root)
{
if (!root) {
return 0;
}
int maximum = 0, minimum = 0;
lengthUtil(root, maximum, minimum, 0);
//returning the result.
return (abs(minimum) + maximum) + 1;
}
Mirror Tree
Your Task:
Just complete the function mirror() that takes node as paramter and convert it into its mirror. The printing is done by the driver code only.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the Tree).
// Function to convert a binary tree into its mirror tree.
void mirror(Node* node) {
if (!node) return;
swap(node->left, node->right);
mirror(node->left);
mirror(node->right);
}Convert a Binary Tree to a Circular Doubly Link List
Given a Binary Tree, convert it to a Circular Doubly Linked List (In-Place).
The left and right pointers in nodes are to be used as previous and next pointers respectively in converted Circular Linked List.
The order of nodes in the List must be the same as in Inorder for the given Binary Tree.
The first node of Inorder traversal must be the head node of the Circular List.
Example:
The idea can be described using the below steps.
1) Write a general-purpose function that concatenates two given circular doubly lists (This function is explained below).
2) Now traverse the given tree
….a) Recursively convert left subtree to a circular DLL. Let the converted list be leftList.
….a) Recursively convert right subtree to a circular DLL. Let the converted list be rightList.
….c) Make a circular linked list of root of the tree, make left and right of root to point to itself.
….d) Concatenate leftList with the list of the single root node.
….e) Concatenate the list produced in the step above (d) with rightList.
Note that the above code traverses the tree in Postorder fashion. We can traverse in an inorder fashion also. We can first concatenate left subtree and root, then recur for the right subtree and concatenate the result with left-root concatenation.
How to Concatenate two circular DLLs?
Get the last node of the left list. Retrieving the last node is an O(1) operation since the prev pointer of the head points to the last node of the list.
Connect it with the first node of the right list
Get the last node of the second list
Connect it with the head of the list.
Below are implementations of the above idea.
// C++ Program to convert a Binary Tree // to a Circular Doubly Linked List #include(iostream> using namespace std;
// To represents a node of a Binary Tree
struct Node
{
struct Node *left, *right;
int data;
};
// A function that appends rightList at the end
// of leftList.
Node *concatenate(Node *leftList, Node *rightList)
{
// If either of the list is empty
// then return the other list
if (leftList == NULL)
return rightList;
if (rightList == NULL)
return leftList;
// Store the last Node of left List Node *leftLast = leftList->left;
// Store the last Node of right List Node *rightLast = rightList->left;
// Connect the last node of Left List // with the first Node of the right List leftLast->right = rightList; rightList->left = leftLast;
// Left of first node points to // the last node in the list leftList->left = rightLast;
// Right of last node refers to the first // node of the List rightLast->right = leftList;
return leftList; }
// Function converts a tree to a circular Linked List
// and then returns the head of the Linked List
Node *bTreeToCList(Node *root)
{
if (root == NULL)
return NULL;
// Recursively convert left and right subtrees Node *left = bTreeToCList(root->left); Node *right = bTreeToCList(root->right);
// Make a circular linked list of single node // (or root). To do so, make the right and // left pointers of this node point to itself root->left = root->right = root;
// Step 1 (concatenate the left list with the list // with single node, i.e., current node) // Step 2 (concatenate the returned list with the // right List) return concatenate(concatenate(left, root), right); }
// Display Circular Link List
void displayCList(Node *head)
{
cout (( "Circular Linked List is :\n";
Node *itr = head;
do
{
cout (( itr->data ((" ";
itr = itr->right;
} while (head!=itr);
cout (( "\n";
}
// Create a new Node and return its address
Node *newNode(int data)
{
Node *temp = new Node();
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// Driver Program to test above function
int main()
{
Node *root = newNode(10);
root->left = newNode(12);
root->right = newNode(15);
root->left->left = newNode(25);
root->left->right = newNode(30);
root->right->left = newNode(36);
Node *head = bTreeToCList(root); displayCList(head); return 0; } Output:
Circular Linked List is :
25 12 30 10 36 15
Maximum difference between node and its ancestor in Binary Tree
Given a binary tree, we need to find maximum value we can get by subtracting value of node B from value of node A, where A and B are two nodes of the binary tree and A is an ancestor of B. Expected time complexity is O(n).
For example, consider below binary tree
We can have various ancestor-node difference, some of which are given below :
8 – 3 = 5
3 – 7 = -4
8 – 1 = 7
10 – 13 = -3
. . . .
But among all those differences maximum value is 7 obtained by subtracting 1 from 8, which we need to return as result.
As we are given a binary tree, there is no relationship between node values so we need to traverse whole binary tree to get max difference and we can obtain the result in one traversal only by following below steps:
If we are at leaf node then just return its value because it can’t be ancestor of any node. Then at each internal node we will try to get minimum value from left subtree and right subtree and calculate the difference between node value and this minimum value and according to that we will update the result.
As we are calculating minimum value while returning in recurrence, we will check all optimal possibilities (checking node value with minimum subtree value only) of differences and hence calculate the result in one traversal only.
//Function to find the maximum difference.
int maxDiffUtil(Node *t,int *res)
{
//returning Maximum int value if node is null.
if (t == NULL)
return INT_MAX;
//if there are no child nodes then we just return data at current node.
if (t->left == NULL && t->right == NULL)
return t->data;
//recursively calling for left and right subtrees and
//choosing their minimum.
int val = min(maxDiffUtil(t->left, res),
maxDiffUtil(t->right, res));
//updating res if (node value - min value from subtrees) is bigger than res.
*res = max(*res, t->data - val);
//returning minimum value got so far.
return min(val, t->data);
}
//Function to return the maximum difference between any node and its ancestor.
int maxDiff(Node *root)
{
