A binary tree is a data structure with a finite set of nodes consisting of:

  • A unique node with no parents called root and zero or more subtrees.
  • Every node can be connected to an arbitrary number of nodes, called children.
  • Nodes with no children are called external nodes or leaves.
  • Internal nodes are the ones that they are not leaves.
  • The Nodes that have the same parent are called siblings.
  • The top node is called the root with no parent-child.
  • The last nodes with no further child nodes are called leaves.

Binary Tree in C++

Binary Tree

Tree traversals

Tree traversal refers to visiting each node only once.

Pre-order traversal – It visits the parent node first and then left and right children
Post-order traversal – It visits the left child, then the right child and then the parent
In-order traversal – It visits the left child, then the parent and the right child
Level-order traversal – it visits nodes by levels from top to bottom and from left to right

Structure of the Tree Node in C++

struct node {
    int key;
    node* left, *right;
};

Create a new node in a Binary tree using C++

The following function will create a new node in the Binary Tree

struct node* newnode(int key)
{
    struct node* temp = new node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return temp;
};

Now call the function above to  add a new node:

node* root = newnode(5);
    root->left = newnode(6);
    root->left->left = newnode(4);
    root->right = newnode(2);
    root->right->left = newnode(3);
    root->right->right = newnode(7);

In-Order Traversal

Let’s traverse Binary Tree using in-order traversal

void inorder(node* temp)
{
    if (temp == NULL) return;
    inorder(temp->left);
    cout << temp->key << " ";
    inorder(temp->right);
}

To display tree in in-order traversal order, call
inorder(root);

Pre-Order Traversal

Let’s traverse Binary Tree using pre-order traversal

void preorder(node* temp)
{
    if (temp == NULL) return;
cout << temp->key << " ";
    preorder(temp->left);
    preorder(temp->right);
}

To display tree in pre-order traversal order, call
preorder(root);

Post-Order Traversal

Let’s traverse Binary Tree using post-order traversal

void postorder(node* temp)
{
    if (temp == NULL) return;
    postorder(temp->left);
    postorder(temp->right);
cout << temp->key << " ";
}

To display tree in post-order traversal order, call
postorder(root);

Level-Order Traversal

Let’s traverse Binary Tree using level-order traversal

To traverse level-order, you need to find the level of the node you are visiting.

void levelorder(node* root)
{
    int h = height(root);
    int i;
    for (i = 1; i <= h; i++)
        letlevelorder(root, i);
}
void letlevelorder(node* root, int level)
{
    if (root == NULL)
        return;
    if (level == 1)
        cout << root->key << " ";
    else if (level > 1)
    {
        letlevelorder(root->left, level-1);
        letlevelorder(root->right, level-1);
    }
}
int height(node* node)
{
    if (node == NULL)
        return 0;
    else
    {
        /* compute the height of each subtree */
        int lheight = height(node->left);
        int rheight = height(node->right);

        /* use the larger one */
        if (lheight > rheight)
            return(lheight + 1);
        else return(rheight + 1);
    }
}

Traversing trees using all four methods

int main()
{
    node* root = newnode(5);
    root->left = newnode(6);
    root->left->left = newnode(4);
    root->right = newnode(2);
    root->right->left = newnode(3);
    root->right->right = newnode(7);

    cout<<"Pre-order Traversal:   ";
    preorder(root);
    cout<<endl;

    cout<<"Post-order Traversal:  ";
    postorder(root);
    cout<<endl;

    cout<<"In-order Traversal:    ";
    inorder(root);
    cout<<endl;

    cout<<"Level-order Traversal: ";
    levelorder(root);
    cout<<endl;
     
    return 0;
}

Recommanded Reading

Last modified: March 24, 2019