A binary tree is one of the most extensively used tree data structures. It is a hierarchical data structure wherein each node has two children, the left child and the right child. A typical binary tree consists of the following components:
1. A root node
2. A left subtree
3. A right subtree
Pre-order = Root -> Left -> Right
Post-order = Left -> Right -> Root
In-order = Left -> Root -> Right
Today's topics:
Topic 1:
Create binary tree
C++ Binary tree creation.
Code:
#include < bits/stdc++.h>
using namespace std;
class Node
{
public:
int val;
Node *left;
Node *right;
Node(int val)
{
this->val = val;
this->left = NULL;
this->right = NULL;
}
};
int main()
{
Node *root = new Node(10);
Node *a = new Node(20);
Node *b = new Node(30);
Node *c = new Node(40);
Node *d = new Node(50);
Node *e = new Node(60);
Node *f = new Node(70);
Node *g = new Node(80);
Node *h = new Node(90);
Node *i = new Node(100);
// connection
root->left = a;
root->right = b;
a->left = c;
a->right = h;
c->right = e;
b->right = d;
d->left = f;
d->right = g;
h->right = i;
return 0;
}
Topic: 2
Pre-order binary tree traversal
Preorder traversal of binary tree is a traversal method, where the root node is visited first, then left subtree and then the right sub tree. Unlike array and linked lists, linear data structures, we have several ways of traversing binary trees due to their hierarchical nature.
Code:
#include < bits/stdc++.h>
using namespace std;
class Node
{
public:
int val;
Node *left;
Node *right;
Node(int val)
{
this->val = val;
this->left = NULL;
this->right = NULL;
}
};
void preorder(Node *root)
{
if (root == NULL)
{
return;
}
cout << root->val << " ";
preorder(root->left);
preorder(root->right);
}
int main()
{
Node *root = new Node(10);
Node *a = new Node(20);
Node *b = new Node(30);
Node *c = new Node(40);
Node *d = new Node(50);
Node *e = new Node(60);
Node *f = new Node(70);
Node *g = new Node(80);
Node *h = new Node(90);
Node *i = new Node(100);
// connection
root->left = a;
root->right = b;
a->left = c;
a->right = h;
c->right = e;
b->right = d;
d->left = f;
d->right = g;
h->right = i;
// call
preorder(root);
return 0;
}
/*
Pre-order = rot -> Left -> right
*/
Topic: 3
Post-order binary tree traversal
Postorder traversal is defined as a type of tree traversal which follows the Left-Right-Root policy such that for each node: The left subtree is traversed first. Then the right subtree is traversed. Finally, the root node of the subtree is traversed.
Code:
#include < bits/stdc++.h>
using namespace std;
class Node
{
public:
int val;
Node *left;
Node *right;
Node(int val)
{
this->val = val;
this->left = NULL;
this->right = NULL;
}
};
void postorder(Node *root)
{
if (root == NULL)
{
return;
}
postorder(root->left);
postorder(root->right);
cout << root->val << " ";
}
int main()
{
Node *root = new Node(10);
Node *a = new Node(20);
Node *b = new Node(30);
Node *c = new Node(40);
Node *d = new Node(50);
Node *e = new Node(60);
Node *f = new Node(70);
Node *g = new Node(80);
Node *h = new Node(90);
Node *i = new Node(100);
// connection
root->left = a;
root->right = b;
a->left = c;
a->right = h;
c->right = e;
b->right = d;
d->left = f;
d->right = g;
h->right = i;
// call
postorder(root);
return 0;
}
Topic: 4
In-order binary tree traversal
In an inorder traversal of a binary tree, we traverse one subtree of a node, then "visit" the node, and then traverse its other subtree. Usually, we traverse the node's left subtree first and then traverse the node's right subtree.
Code:
#include < bits/stdc++.h>
using namespace std;
class Node
{
public:
int val;
Node *left;
Node *right;
Node(int val)
{
this->val = val;
this->left = NULL;
this->right = NULL;
}
};
void inorder(Node *root)
{
if (root == NULL)
{
return;
}
inorder(root->left);
cout << root->val << " ";
inorder(root->right);
}
int main()
{
Node *root = new Node(10);
Node *a = new Node(20);
Node *b = new Node(30);
Node *c = new Node(40);
Node *d = new Node(50);
Node *e = new Node(60);
Node *f = new Node(70);
Node *g = new Node(80);
Node *h = new Node(90);
Node *i = new Node(100);
// connection
root->left = a;
root->right = b;
a->left = c;
a->right = h;
c->right = e;
b->right = d;
d->left = f;
d->right = g;
h->right = i;
// call
inorder(root);
return 0;
}
Github link here
Today's topics:
Topic 1: Level Order Tree Print
A Level Order Traversal is a traversal which always traverses based on the level of the tree. So, this traversal first traverses the nodes corresponding to Level 0, and then Level 1, and so on, from the root node. In the example Binary Tree above, the level order traversal will be: (Root)
Create a tree in level order:
1. Whenever a new Node is added to the binary tree, the address of the node is pushed into a queue.
2. Node addresses will stay in the queue until both its children's Nodes do not get filled.
3. Once both the children's Nodes get filled up, the parent Node is popped from the queue.
Solution:
#include < bits/stdc++.h>
using namespace std;
class Node
{
public:
int val;
Node *left;
Node *right;
Node(int val)
{
this->val = val;
this->left = NULL;
this->right = NULL;
}
};
void level_order(Node *root)
{
if (root == NULL)
{
cout << "Tree nai" << endl;
return;
}
queue q;
q.push(root);
while (!q.empty())
{
// 1. ber kore ana
Node *f = q.front();
q.pop();
// 2. jabotiyo ja kaj ache
cout << f->val << " ";
// 3. tar children gulo ke rakha
if (f->left)
q.push(f->left);
if (f->right)
q.push(f->right);
}
}
int main()
{
Node *root = new Node(10);
Node *a = new Node(20);
Node *b = new Node(30);
Node *c = new Node(40);
Node *d = new Node(50);
Node *e = new Node(60);
Node *f = new Node(70);
Node *g = new Node(80);
Node *h = new Node(90);
Node *i = new Node(100);
// connection
root->left = a;
root->right = b;
a->left = c;
a->right = h;
c->right = e;
b->right = d;
d->left = f;
d->right = g;
h->right = i;
level_order(root);
return 0;
}
Topic 2: Input Binary Tree
Code:
#include < bits/stdc++.h>
using namespace std;
class Node
{
public:
int val;
Node *left;
Node *right;
Node(int val)
{
this->val = val;
this->left = NULL;
this->right = NULL;
}
};
Node *input_tree()
{
int val;
cin >> val;
Node *root;
if (val == -1)
root = NULL;
else
root = new Node(val);
queue q;
if (root)
q.push(root);
while (!q.empty())
{
// 1. Remove
Node *p = q.front();
q.pop();
// 2. All work
int l, r;
cin >> l >> r;
Node *myLeft;
Node *myRight;
if (l == -1)
myLeft = NULL;
else
myLeft = new Node(l);
if (r == -1)
myRight = NULL;
else
myRight = new Node(r);
p->left = myLeft;
p->right = myRight;
// 3. push children
if (p->left)
q.push(p->left);
if (p->right)
q.push(p->right);
}
return root;
}
void level_order(Node *root)
{
if (root == NULL)
{
cout << "Tree Not Found!" << endl;
return;
}
queue q;
q.push(root);
while (!q.empty())
{
// 1. Remove
Node *f = q.front();
q.pop();
// 2. All work
cout << f->val << " ";
// 3. keep children
if (f->left)
q.push(f->left);
if (f->right)
q.push(f->right);
}
}
int main()
{
Node *root = input_tree();
level_order(root);
return 0;
}
Topic 3 : Count number of nodes
Code:
#include < bits/stdc++.h>
using namespace std;
class Node
{
public:
int val;
Node *left;
Node *right;
Node(int val)
{
this->val = val;
this->left = NULL;
this->right = NULL;
}
};
Node *input_tree()
{
int val;
cin >> val;
Node *root;
if (val == -1)
root = NULL;
else
root = new Node(val);
queue q;
if (root)
q.push(root);
while (!q.empty())
{
// 1. ber kore ano
Node *p = q.front();
q.pop();
// 2. jabotiyo ja kaj ache
int l, r;
cin >> l >> r;
Node *myLeft;
Node *myRight;
if (l == -1)
myLeft = NULL;
else
myLeft = new Node(l);
if (r == -1)
myRight = NULL;
else
myRight = new Node(r);
p->left = myLeft;
p->right = myRight;
// 3. children gulo ke push koro
if (p->left)
q.push(p->left);
if (p->right)
q.push(p->right);
}
return root;
}
int count(Node *root)
{
if (root == NULL)
return 0;
int l = count(root->left);
int r = count(root->right);
return l + r + 1;
}
int main()
{
Node *root = input_tree();
cout << count(root) << endl;
return 0;
}
Topic 4: Count Leaf Node
Code:
#include < bits/stdc++.h>
using namespace std;
class Node
{
public:
int val;
Node *left;
Node *right;
Node(int val)
{
this->val = val;
this->left = NULL;
this->right = NULL;
}
};
Node *input_tree()
{
int val;
cin >> val;
Node *root;
if (val == -1)
root = NULL;
else
root = new Node(val);
queue q;
if (root)
q.push(root);
while (!q.empty())
{
// 1. Pull
Node *p = q.front();
q.pop();
// 2. All work
int l, r;
cin >> l >> r;
Node *myLeft;
Node *myRight;
if (l == -1)
myLeft = NULL;
else
myLeft = new Node(l);
if (r == -1)
myRight = NULL;
else
myRight = new Node(r);
p->left = myLeft;
p->right = myRight;
// 3. Push children
if (p->left)
q.push(p->left);
if (p->right)
q.push(p->right);
}
return root;
}
int count_leaf(Node *root)
{
if (root == NULL)
return 0;
if (root->left == NULL && root->right == NULL)
{
return 1;
}
else
{
int l = count_leaf(root->left);
int r = count_leaf(root->right);
return l + r;
}
}
int main()
{
Node *root = input_tree();
cout << count_leaf(root) << endl;
return 0;
}
// 10 20 50 30 40 70 60 -1 -1 -1 -1 -1 80 -1 -1 -1 -1
// ANS= 4
Topic 5: Max Height
Code:
#include < bits/stdc++.h>
using namespace std;
class Node
{
public:
int val;
Node *left;
Node *right;
Node(int val)
{
this->val = val;
this->left = NULL;
this->right = NULL;
}
};
Node *input_tree()
{
int val;
cin >> val;
Node *root;
if (val == -1)
root = NULL;
else
root = new Node(val);
queue q;
if (root)
q.push(root);
while (!q.empty())
{
// 1. ber kore ano
Node *p = q.front();
q.pop();
// 2. jabotiyo ja kaj ache
int l, r;
cin >> l >> r;
Node *myLeft;
Node *myRight;
if (l == -1)
myLeft = NULL;
else
myLeft = new Node(l);
if (r == -1)
myRight = NULL;
else
myRight = new Node(r);
p->left = myLeft;
p->right = myRight;
// 3. children gulo ke push koro
if (p->left)
q.push(p->left);
if (p->right)
q.push(p->right);
}
return root;
}
int maxHeight(Node *root)
{
if (root == NULL)
return 0;
int l = maxHeight(root->left);
int r = maxHeight(root->right);
return max(l, r) + 1;
}
int main()
{
Node *root = input_tree();
cout << maxHeight(root) << endl;
return 0;
}
// 10 20 30 70 150 120 40 80 90 -1 -1 130 -1 60
50 -1 -1 100 -1 -1 140 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1