A tree is a non-linear data structure where each node is connected to several nodes with the help of pointers or references.

This is a sample tree shown above.

✨Basic Tree Terminologies

• Root: The root of a tree is the first node of the tree. In the above image, the root node is node A.

• Edge: An edge is a link connecting any two nodes in the tree. For example, in the above image, there is an edge between nodes G and J.

• Leaf Node: A node is said to be a leaf node if there are no children. In the above tree, node J is one of the leaf node.

• Height of a Tree: The height of a tree is defined as the total number of levels in the tree or the length of the path from the root node to the leaf node. The height of the above tree is 3.

✨Binary Tree

A Tree is said to be a binary tree if all of its nodes have at most 2 children. That is, all of its nodes can have either no child, 1 or 2 child nodes.

🍁Properties of Binary Tree

• The maximum number of nodes at level 'n' of a binary tree is (2^{n- 1}). The level of the root is 1. This can be proved. For root, n=1, number of nodes = 2^1-1 = 1. Assume that the maximum number of nodes on level n is 2^n-1. Since in a binary tree, every node has at most 2 children, the next level would have twice nodes, i.e 2*2^n-1.

• Maximum number of nodes in a binary tree of height 'h' is (2^h – 1).

  Here the height of a tree is the maximum number of nodes on the root-to-leaf path. The height of a tree with a single node is considered as 1. This result can be derived from point 2 above. A tree has maximum nodes if all levels have maximum nodes. So the maximum number of nodes in a binary tree of height h is 1+2+4+..+ 2^h-1. This is a simple geometric series with h terms and the sum of this series is 2^h-1. In some books. the height of the root is considered 0. In that convention, the above formula becomes 2^h+1 – 1.

• In a Binary Tree with N nodes, the maximum possible height or the minimum number of levels is Log₂(N+1). If we consider the convention where the height of a leaf node is considered 0, then the above formula for minimum possible height becomes Log₂(N+1) – 1.

• A Binary Tree with L leaves has at least (Log₂L + 1) levels. A binary tree has a maximum number of leaves (and a minimum number of levels) when all levels are filled.

• In a Binary tree in which every node has 0 or 2 children, the number of leaf nodes is always one more than nodes with two children.

  L = T + 1
  Where L = Number of leaf nodes
     T = Number of internal nodes with two children
  

🍁Types of Binary tree

Based on the structure and number of parents and children nodes, a Binary Tree is classified into the following common types.

🍀Full Binary Tree

A binary tree is full if every node has either 0 or 2 children. The following are examples of a full binary tree. We can also say that a full binary tree is a tree in which all nodes except leaf nodes have two children.

🍀Complete Binary Tree

A binary tree is a complete tree if all levels are filled except possibly the last level and have all keys as left as possible.

🍀Perfect Binary Tree

A binary tree is a perfect binary tree when all interval nodes have two children and all the leaf nodes are at the same level.

✨Implementation of Binary Tree

Let us create a simple tree with 4 nodes.

#include<bits/stdc++.h>
using namespace std;

class Node{
public:
int data;
Node* left;
Node* right;
Node(int val){
data = val;
left = NULL;
right = NULL;
}
};

int main(){
Node* root = new Node(1);
/* following is the tree after above statement

  1
/   \
NULL NULL

*/
root->left = new Node(2);
root->right = new Node(3);
/* 2 and 3 become left and right children of 1
       1
   /       \
  2        3
/   \     /   \
NULL NULL NULL NULL
*/
root->left -> left = new Node(4);
/* 4 becomes left child of 2
    1
 /     \
 2       3
/ \    /    \
4  NULL NULL NULL
/  \
NULL NULL
*/
return 0; 
}

✨Binary Tree Traversals

Linear data structures(array, linked list, queues, stacks, etc) have only one logical way to traverse them, trees can be traversed in different ways.

The different ways are:

• Inorder (Left, root, right): 5, 2, 6, 1, 3

• Preorder (root, left, right): 1, 2, 5, 6, 3

• Postorder (left, right, root): 5, 6, 2, 3, 1

Let's code the different tree traversals.

• Inorder Traversal: In inorder traversal, a node is processed after processing all the nodes in its left subtree. The right subtree of the node is processed after processing the node itself.

  Algorithm:

  1. Traverse the left subtree i.e. call inorder (left->subtree)

  2. Visit the root.

  3. Traverse the right subtree i.e call inorder (right ->subtree)]

```cpp
#include<bits/stdc++.h>
using namesspace std;

struct Node{
int data;
struct Node* left, right;
Node(int data){
    this->data = data;
    left = right = NULL;
}
};
void printInorder(struct Node* node){
if(node = NULL){
return;
}
printInorder(node->left);

cout<<node->data<<" ";
printInorder(node->right);
}
int main(){
//           1
    //     /  \
    //    2    3
    //   / \    
    //  4   5
struct Node*root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left ->right = new Node(5);

cout<<"\n Inorder traversal of the tree is";
printInorder(root);
return 0;
}
```

• Preorder Traversal: In preorder traversal, a node is processed before processing any of the nodes in its subtree.

  Algorithm:

  1. Visit the root.

  2. Traverse the left subtree i.e call preorder(left-> subtree).

  3. Traverse the right subtree i.e call preorder (right->subtree).

```cpp
#include<bits/stdc++.h>
using namespace std;

struct Node{
int data;
struct Node* left, *right;
Node(int data){
this->data = data;
left = right = NULL;
}
};
void printPreorder(struct Node* node){
if(node == NULL){
return;
}
cout<<node->data;
printPreorder(node->left);
printPreorder(node->right);
}

int main(){
struct Node *root = new Node(1);
root -> left = new Node(2);
root -> right = new Node(3);
root ->left ->left = new Node(4);
root ->left ->right = new Node(5);

cout<<"Preorder traversal of the binary tree is";
printPreorder(root);
return 0;
}
```

• Postorder Traversal: In post-order traversal, a node is processed after processing all the nodes in its subtree.

  Algorithm:

  1. Traverse the left subtree i.e call postorder (left->subtree)

  2. Traverse the right subtree i.e call postorder (right -> subtree)

  3. Visit the root.

```cpp
#include<bits/stdc++.h>
using namespace std;

struct Node{
int data;
struct Node *left, *right;
Node(int data){
this->data = data;
left = right = NULL;
}
};

void printPostorder(struct Node *node){
    if(node == NULL){
        return;
}
printPostorder(node->left);
printPostorder(node->right);
cout<< node->data<<" ";
}

int main(){
struct Node *root = new Node(1);
root ->left = new Node(2);
root ->right = new Node(3);
root ->left ->right = new Node(5);
root ->left ->left = new Node(4);

cout<<"Postorder traversal of the binary tree is:";
printPostorder(root);
return 0;
}
```

✨Level Order Traversal

In the level order traversal, the binary tree is traversed level-wise starting from the first to the last level sequentially.

🍁Algorithm

1. Create an empty queue q.

2. Push the root node of a tree to q. That is, q.push(root).

3. Loop while the queue is not empty.

   • Pop the top node from the queue and print the node.

   • Enqueue node's children (first left then right children) to q.

   • Repeat the process until the queue is not empty.

#include <bits/stdc++.h>
using namespace std;

struct Node{
int data;
struct Node *left, *right;
};
Node *newNode(int data){
Node *temp = new Node;
temp -> data = data;
temp -> left = temp ->right = NULL;
return temp;
}

void printLevelOrder(Node *root){
if(root == NULL){
return;
}

queue<Node*> q; // Create an empty queue for LOT
q.push(root); //enqueue root and initialize height

while(q.empty() == false){
    //print front of queue and remiove it from queue
Node *node = q.front();
cout<< node->data<<" ";
q.pop();

/* Enqueue left child */
if(node->left !=NULL){
q.push(node->left);
}
/*Enqueue right child*/
if(node->right !=NULL){
q.push(node->right);
}
}
}
int main(){
    //      1
    //     / \
    //    2   3
    //   / \
    //  4   5
Node *root = newNode(1);
root -> left = newNode(2);
root -> right = newNode(3);
root -> left ->left = newNode(4);
root ->left -> right = newNode(5);

cout<<"Level order traversal of the binary tree is \n";
printLevelOrder(root);
return 0;
}

Time Complexity: O(N), where N is the number of nodes in the Tree.
Auxiliary Space: O(N)

✨Check for Balanced Binary Tree

A height-balanced binary tree is a binary tree in which the height of the left subtree and right subtree of any node does not differ by more than 1 and both the left and right subtree are also height-balanced.

Example: The tree on the left is a height-balanced binary tree. Whereas the tree on the right is not height-balanced. Because the left subtree of the root has a height that is 2 more than the height of the right subtree.

Below is the implementation of the above approach.

#include<bits/stdc++.h>
using namespace std;

struct Node{
int data;
struct Node *left, *right;
Node(int data){
this->data = data;
left = right = NULL;
}
};

//function to calculate height of the tree
int height(Node *node){
if(node ==NULL){
return 0;
}
//if the tree is not empty
//height = 1 + max of left height
// and right height
return 1+max(height(node ->left), height(node ->right));
}

//returns true if binary tree
//with root as root is height-balanced
bool isBalanced(Node *root){
//for height of left 
int lh;
// for height of right subtree
int rh;
// if tree is empty then return true
if(root == NULL){
return 1;
}        
lh = height(root->left);
rh = height(root->right);

if(abs(lh - rh)<=1 && isBalanced(root->left) && isBalanced(root->right)){
return 1;
}    
return 0;
}
int main()
{
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->left->left->left = new Node(8);

    if (isBalanced(root))
        cout << "Tree is balanced";
    else
        cout << "Tree is not balanced";
    return 0;
}

Time Complexity: O(n^2) in the case of a full binary tree.
Auxiliary Space: O(n) space for call stack since using recursion.

Efficient approach

Calculating the height in the same recursion rather than calling a height() function separately.

• For each node make two recursion calls - one for the left subtree and the other for the right subtree.

• Based on the heights returned from the recursion calls, decide if the subtree whose root is the current node is height-balanced or not.

• If it is balanced then return the height of that subtree. Otherwise, return -1 to denote that the subtree is not height-balanced.

#include<bits/stdc++.h>
using namespace std;

struct Node{
int data;
struct Node *left, *right;
Node(int data)
{
this ->data = data;
left = right = NULL;
}
};

int isBalanced(Node * root){
    if(root==NULL){
        return ;
}
int lh = isBalanced(root->left);
if(lh == -1){
return -1;
}
int rh = isBalanced(root->right);
if(rh == -1){
return -1;
}
if(abs(lh - rh)>1){
return -1;
}
else{
return max(lh, rh) +1;
}
}
int main()
{
    Node* root = new Node(10);
    root->left = new Node(5);
    root->right = new Node(30);
    root->right->left = new Node(15);
    root->right->right = new Node(20);

    if (isBalanced(root) > 0)
        cout << "Balanced";
    else
        cout << "Not Balanced";
    return 0;
}

Time Complexity: O(n)

Auxiliary Space: O(n)

✨LCA in Binary Tree

The LCA of any two nodes N1 and N2 is defined as the common ancestor of both the nodes which is closest to them. That is the distance of the common ancestor from the nodes N1 and N2 should be the least possible.

🍁Finding LCA

Method 1: To find the LCA of the given nodes will be the last common node in the paths from the root node to the given node.

For example: consider the above-given tree and nodes 8 and 10.

• The path from the root to node 8: [1,2,4,8]

• The path from the root to node 10: [1,2,5,10]

The last common node is 2 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.

#include<bits/stdc++.h>
using namespace std;

struct Node {
int data;
struct Node *left, *right;
Node(int data){
this->data = data;
left = right = NULL;
}
};

bool findPath(Node *root, vector<int> &path, int k){
if(root == NULL){
return false;
}
//store this node in path vector.
//the node will be removed if
//not in path from root to k
path.push_back(root->data);
if(root->data == k){
return true;
}
// check if k is found in left or right subtree
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){
vector<int> path1, path2;
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 = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);

    cout << "LCA(4, 5) = " << findLCA(root, 4, 5);
    cout << "\nLCA(4, 6) = " << findLCA(root, 4, 6);
    cout << "\nLCA(3, 4) = " << findLCA(root, 3, 4);
    cout << "\nLCA(2, 4) = " << findLCA(root, 2, 4);

    return 0;
}

Time Complexity: O(N)

Space Complexity: O(N)

Method 2: 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 can find LCA using single traversals of the 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 the root, then the root is LCA(assuming that both keys are present). 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 the other key present in the right subtree is the LCA. If both keys lie in the left subtree, then the left subtree has LCA also, otherwise, LCA lies in the right subtree.

#include<bits/stdc++.h>
using namespace std;

struct Node{
int data;
Node *left, *right;
};
Node *newnode(int data){
Node *temp = new Node();
temp -> data = data;
temp -> left = NULL;
temp -> right = NULL;
return temp;
}


Node *findLCA(Node *root, int n1, int n2){
if(root==NULL){
return NULL;
}
/*
If either n1 or n2 matches with root's data, report the presence by returing root
*/
if(root->data ==n1 || root->data ==n2){
return root;
}
Node *left_lca =findLCA(root->left, n1, n2);
Node *right_lca  = findLCA(root->right, n1, n2);

/*
If both of the above calls return non-NULL
then one key is present in once subtree and other is present in other is present in other
*/
if(left_lca && right_lca){
return root;
}
//otherwise check if left subtree or
//right subtree is LCA
return(left_lca !=NULL) ? left_lca : right_lca;
}

// Driver Code
int main()
{
    // Let us create binary tree given in the above example
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);

    cout << "LCA(4, 5) = " << findLCA(root, 4, 5)->key;
    cout << "nLCA(4, 6) = " << findLCA(root, 4, 6)->key;
    cout << "nLCA(3, 4) = " << findLCA(root, 3, 4)->key;
    cout << "nLCA(2, 4) = " << findLCA(root, 2, 4)->key;

    return 0;
}

✨References

1. Geeksforgeeks