Binary Tree is a data structure with following properties:
- Every node will have at most 2 children.
- A node can not have more than one parent.
- The nodes which have neither left, nor right child i.e., 0 children, are called Leaf nodes.
- The Root node has no parent.
In the above Binary tree 5 is the root node. 20, 3, and 9 are Leaf nodes.
Binary Search Trees (BST) are Binary trees with following following properties:
- All nodes in the left sub-tree of a node are smaller than the data stored in the node.
- All nodes in the right sub-tree of a node are larger than the data stored in the node.
In the above BST, all the nodes in the right sub-tree of root node(5), have values greater than 5, and all the nodes in the left sub-tree have values smaller than 5.
Q1. Write a recursive program to traverse a Binary Search Tree in pre-order.
Solution:
Pre-order traversal of a Binary Tree is defined as visiting a node before visiting its children.
Algorithm:
For every node n:
* Visit n
* Visit left(n)
* Visit right(n)
Implementation:
#include <stdio.h>
#include <stdlib.h>
/*structure of BST node*/
struct BSTNode
{
int data;
BSTNode *left;
BSTNode *right;
};
/*recursive function for pre-order traversal of BST*/
void preOrder(BSTNode *root)
{
if(root == NULL)
return;
printf("%d \n", root->data);
preOrder(root->left);
preOredr(root->right);
}
Q2. Write a program to print the level-order traversal of a Binary Tree.
Solution:
#include <stdio.h>
#include <queue>
/*Node of a Binary Tree*/
struct Node
{
int data;
Node *left;
Node *right;
};
/*Function to print the nodes of a Binary Tree in level-order*/
void printLevel(Node *root)
{
queue<Node *> Q;
if(root == NULL)
{
return;
}
Q.insert(root);
while(!Q.empty())
{
Node *n = Q.front();
printf("%d ", n->data);
Q.pop();
if(n->left != NULL)
Q.push(n->left);
if(n->right != NULL)
Q.push(n->right);
}
}
Time Complexity: O(n)
Q3. Write an iterative program to print the in-order traversal of a Binary Search Tree.
Solution:
#include <iostream>
#include <stack>
using namespace std;
// structure of Binary Tree Node
struct Node
{
int data;
Node *left; // pointer to left sub-tree
Node *right; // pointer to right sub-tree
// Constructors
Node(){data = 0; left = NULL; right = NULL;}
Node(int val){data = val; left = NULL; right = NULL;}
};
//Code for in-Order Traversal of BST
void inOrderIterative1(Node *root)
{
if(root == NULL)
return;
stack<Node *> S;
Node *n = root;
S.push(n);
while(n->left)
{
n = n->left;
S.push(n);
}
while(!S.empty())
{
n = S.top();
S.pop();
cout << n->data << " ";
if(n->right)
{
n = n->right;
S.push(n);
while(n->left)
{
n = n->left;
S.push(n);
}
}
}
}
void inOrderIterative2(Node *root)
{
if(root==NULL)
return;
stack<Node *> S;
Node *curr = root;
bool completed = false;
while(!completed)
{
if(curr)
{
S.push(curr);
curr = curr->left;
}
else
{
if(!S.empty())
{
curr = S.top();
cout << curr->data << " ";
S.pop();
curr = curr->right;
}
else
completed = true;
}
}
}
int main()
{
//-------------0 1 2 3 4 5 6 7 8 9 10
int arr[11] = {3, 4, 5, 6, 10, 14, 15, 16, 20, 25, 30};
Node nodes[11];
for(int i = 0; i<11; i++)
{
nodes[i].data = arr[i];
}
// Build the tree
nodes[4].left=&nodes[2]; nodes[4].right=&nodes[8]; //node 10
nodes[2].left=&nodes[1]; nodes[2].right=&nodes[3]; //node 5
nodes[8].left=&nodes[6]; nodes[8].right=&nodes[9]; //node 20
nodes[6].left=&nodes[5]; nodes[6].right=&nodes[7]; //node 15
nodes[1].left = &nodes[0]; //node 4
nodes[9].right = &nodes[10]; //node 25
/*---------------------------------------------------
10
/ \
5 20
/ \ / \
4 6 15 25
/ / \ \
3 14 16 30
----------------------------------------------------*/
Node *root = &nodes[4];
inOrderIterative1(root); //calling 1st method
cout << endl;
inOrderIterative2(root); // calling 2nd method
return 0;
}
Output : 3 4 5 6 10 14 15 16 20 25 30
3 4 5 6 10 14 15 16 20 25 30
Time Complexity : O(n)
Note: In-Order traversal of a Binary Search Tree prints the nodes in ascending order of their data.
Q4. Write a program to print all the paths from root to leaves of a Binary Tree.
Solution:
#include <iostream>
#include <queue>
using namespace std;
// structure of Binary Tree Node
struct Node
{
int data;
Node *left; // pointer to left sub-tree
Node *right; // pointer to right sub-tree
// Constructors
Node(){data = 0; left = NULL; right = NULL;}
Node(int val){data = val; left = NULL; right = NULL;}
};
//Code for printing paths of Binary tree
{
if(root == NULL)
return;
Q.push(root);
if(root->left==NULL && root->right==NULL)
{
//print path
while(!Q.empty())
{
cout << Q.front()->data << " ";
Q.pop();
}
cout << endl;
}
else
{
printPaths(root->left, Q);
printPaths(root->right, Q);
}
}
int main()
{
//-------------0 1 2 3 4 5 6 7 8 9 10
int arr[11] = {3, 4, 5, 6, 10, 14, 15, 16, 20, 25, 30};
Node nodes[11];
for(int i = 0; i<11; i++)
{
nodes[i].data = arr[i];
}
// Build the tree
nodes[4].left=&nodes[2]; nodes[4].right=&nodes[8]; //node 10
nodes[2].left=&nodes[1]; nodes[2].right=&nodes[3]; //node 5
nodes[8].left=&nodes[6]; nodes[8].right=&nodes[9]; //node 20
nodes[6].left=&nodes[5]; nodes[6].right=&nodes[7]; //node 15
nodes[1].left = &nodes[0]; //node 4
nodes[9].right = &nodes[10]; //node 25
/*---------------------------------------------------
10
/ \
5 20
/ \ / \
4 6 15 25
/ / \ \
3 14 16 30
----------------------------------------------------*/
Node *root = &nodes[4];
queue<Node *> Q;
printPaths(root, Q);
return 0;
}
Output :
10 5 4 3
10 5 6
10 20 15 14
10 20 15 16
10 20 25 30
Time Complexity : O(n)
Q5. Given the pre-order and in-order traversal of a Binary Tree, find out the structure of the Tree.
pre-order : 10, 5, 4, 3, 6, 20, 15, 14, 16, 25, 30
in-order : 3, 4, 5, 6, 10, 14, 15, 16, 20, 25, 30
Solution:
Algorithm:
In pre-order Traversal of a Binary Tree, we visit the root node first, then left node, and finally right node.
So, in pre-order traversal, root node is printed first.
Here, 1st element in pre-order is 10.
=> Root Node = 10.
Now, we know that in in-order traversal of a BT, left sub-Tree is printed first, followed by Root and then Right sub-Tree.
So, all elements to the left of 10(Root), lie in the left sub-tree, and all elements to the right of 10 lie in right sub-tree.
in-order : 3, 4, 5, 6, [10], 14, 15, 16, 20, 25, 30
=> Root = 10
Left sub-tree (T1) = {3, 4, 5, 6}
Right sub-tree (T2) = {14, 15, 16, 20, 25, 30}
So, we have broken the problem into 2 small sub-problems. If we can find the structure of T1 and T2, we can get the structure of entire tree.
T = (T1) Root (T2)
[10]
/ \
/ \
(3, 4, 5, 6) (14, 15, 16, 20, 25, 30)
Proceeding similarly for T1 and T2 , we get:
[10]
/ \
/ \
[5] [20]
/ \ / \
/ \ / \
[4] [6] [15] [25]
/ / \ \
/ / \ \
[3] [14] [16] [30]
In this case, co-incidently the Binary Tree obtained is also a Binary Search Tree. But, the method is generic, and is valid for any Binary Tree.
Q6 Given a binary tree, print all the paths from root to leaf.
Algorithm:
1. If root is NULL, return as there is nothing to print;
2. Push root into a Queue (or a sufficiently large size array).
3. Recursively call printPath function for left child and right child. Pass the Queue as value(not by reference).
Now both left as well as right sub-trees will have their own copy of Q with root node in it.
4. If we reach a leaf node, one by one print all the elements of the Queue.
Solution:
#include <iostream>
#include <queue>
using namespace std;
/* structure of a tree node */ struct Node{
int data;
Node *left;
Node *right;
Node(int val=0):data(val), left(NULL), right(NULL){}
};
/*
main function which prints all the paths from root to leaves
*/ void rootToLeafPath(Node* root, queue<int> Q){
if(root == NULL)
return;
Q.push(root->data);
if(root->left == NULL && root->right == NULL){
while (!Q.empty())
{
cout << Q.front() << " ";
Q.pop();
}
cout << endl;
}
else{
rootToLeafPath(root->left, Q);
rootToLeafPath(root->right, Q);
}
}
/* main function */ int main(int _Argc, char* argv[]){
/*
[10]
/ \
[15] [20]
/ \ /
[7] [12] [30]
*/
Node nodes[6] = {10, 15, 20, 7, 12, 30};
nodes[0].left = &nodes[1]; nodes[0].right = &nodes[2];
nodes[1].left = &nodes[3]; nodes[1].right = &nodes[4];
nodes[2].left = &nodes[5];
queue<int> Q;
rootToLeafPath(&nodes[0], Q);
return 0;
}
Output:
10 15 7
10 15 12
10 20 30
Q7 Given a binary tree, print all the Diagonal Sums.
Algorithm:
1. If root is NULL, return as there is nothing to print;
2. All nodes and its right child lie in the same diagonal.
3. Left child of a node lies in the next diagonal.
1
/ \
2 3
/ \ / \
9 6 4 5
\ / / \
10 11 12 7
Solution:
#include <iostream>
#include <vector>
using namespace std;
struct Node{
int data;
Node *left;
Node *right;
Node(int val):data(val), left(NULL), right(NULL){}
};
void printDiagonalSum(Node* root, unsigned index, vector<int>& Sum){
if(!root)
return;
if(Sum.size() < index+1)
Sum.push_back(0);
Sum[index] += root->data;
printDiagonalSum(root->right, index, Sum);
printDiagonalSum(root->left, index+1, Sum);
}
int main(){
Node nodelist[11] = { Node(1),Node(2),Node(3),Node(4),Node(5),Node(6), Node(7),Node(9),Node(10),Node(11),Node(12)};
nodelist[0].left = nodelist+1;
nodelist[0].right = nodelist+2;
nodelist[1].left = nodelist+7;
nodelist[1].right = nodelist+5;
nodelist[2].left = nodelist+3;
nodelist[2].right = nodelist+4;
nodelist[3].left = nodelist+10;
nodelist[3].right = nodelist+6;
nodelist[5].left = nodelist+9;
nodelist[7].right = nodelist+8;
vector<int> vecSum;
printDiagonalSum(nodelist, 0, vecSum);
for(vector<int>::iterator it=vecSum.begin(); it != vecSum.end(); ++it)
cout << *it << " ";
return 0;
}
Output : 9 19 42
No comments :
Post a Comment