Trees

Tree represents the nodes connected by edges. We will discuss binary tree or binary search tree specifically. Binary Tree is a special datastructure used for data storage purposes. A binary tree has a special condition that each node can have a maximum of two children. A binary tree has the benefits of both an ordered array and a linked list as search is as quick as in a sorted array and insertion or deletion operation are as fast as in linked list.

Important Terms

Following are the important terms with respect to tree.

Path − Path refers to the sequence of nodes along the edges of a tree.

Root − The node at the top of the tree is called root. There is only one root per tree and one path from the root node to any node.

Parent − Any node except the root node has one edge upward to a node called parent.

Child − The node below a given node connected by its edge downward is called its child node.

Leaf − The node which does not have any child node is called the leaf node.

Subtree − Subtree represents the descendants of a node.

Visiting − Visiting refers to checking the value of a node when control is on the node.

Traversing − Traversing means passing through nodes in a specific order.

Levels − Level of a node represents the generation of a node. If the root node is at level 0, then its next child node is at level 1, its grandchild is at level 2, and so on.

keys − Key represents a value of a node based on which a search operation is to be carried out for a node.

Binary search tree

Binary Search Tree is a node-based binary tree data structure which has the following properties:

The left subtree of a node contains only nodes with keys lesser than the node’s key.

The right subtree of a node contains only nodes with keys greater than the node’s key.

The left and right subtree each must also be a binary search tree.

There must be no duplicate nodes.

Program for binary search tree

    // C++ program to demonstrate insertion
    // in a BST recursively.
    #include 
    using namespace std;

    class BST
    {
        int data;
        BST *left, *right;

    public:
        // Default constructor.
        BST();

        // Parameterized constructor.
        BST(int);

        // Insert function.
        BST* Insert(BST*, int);

        // Inorder traversal.
        void Inorder(BST*);
    };

    // Default Constructor definition.
    BST ::BST()
        : data(0)
        , left(NULL)
        , right(NULL)
    {
    }

    // Parameterized Constructor definition.
    BST ::BST(int value)
    {
        data = value;
        left = right = NULL;
    }

    // Insert function definition.
    BST* BST ::Insert(BST* root, int value)
    {
        if (!root)
        {
            // Insert the first node, if root is NULL.
            return new BST(value);
        }

        // Insert data.
        if (value > root->data)
        {
            // Insert right node data, if the 'value'
            // to be inserted is greater than 'root' node data.

            // Process right nodes.
            root->right = Insert(root->right, value);
        }
        else
        {
            // Insert left node data, if the 'value'
            // to be inserted is greater than 'root' node data.

            // Process left nodes.
            root->left = Insert(root->left, value);
        }

        // Return 'root' node, after insertion.
        return root;
    }

    // Inorder traversal function.
    // This gives data in sorted order.
    void BST ::Inorder(BST* root)
    {
        if (!root) {
            return;
        }
        Inorder(root->left);
        cout << root->data << endl;
        Inorder(root->right);
    }

    // Driver code
    int main()
    {
        BST b, *root = NULL;
        root = b.Insert(root, 50);
        b.Insert(root, 30);
        b.Insert(root, 20);
        b.Insert(root, 40);
        b.Insert(root, 70);
        b.Insert(root, 60);
        b.Insert(root, 80);

        b.Inorder(root);
        return 0;
    }

Types of trees

1.General Tree
2.Binary Tree
3.Binary Search Tree
4.AVL Tree
5.Red-Black Tree
6.N-ary Tree