Tree

Tree: Tree is hierarchical data structure, where array, linked list, stack and queue are linear data structure.

why should we use tree data structure? #

• To store information which naturally forms hierarchy, i.e. file system on a computer
• Tree provides moderate search and insertion speed, better then linked list slower then array
• Tree does’t have upper limit like linked list

Tree vocabulary #

Root: top most node

Children: under some element or root

Parent: element directly under some element

Leaves: element which has no children

BST #

The following is definition of Binary Search Tree(BST) according to WikiPedia

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 less 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.

The above properties of Binary Search Tree provide an ordering among keys so that the operations like search, minimum and maximum can be done fast. If there is no ordering, then we may have to compare every key to search a given key.

Searching a key
To search a given key in Bianry Search Tree, we first compare it with root, if the key is present at root, we return root. If key is greater than root’s key, we recur for right subtree of root node. Otherwise we recur for left subtree.

// C function to search a given key in a given BST
struct node* search(struct node* root, int key)
{
// Base Cases: root is null or key is present at root
if (root == NULL || root->key == key)
return root;

// Key is greater than root's key
if (root->key < key)
   return search(root->right, key);

// Key is smaller than root's key
return search(root->left, key);

}
Insertion of a key
A new key is always inserted at leaf. We start searching a key from root till we hit a leaf node. Once a leaf node is found, the new node is added as a child of the leaf node.

     100                               100
    /   \        Insert 40            /    \
  20     500    --------->          20     500 
 /  \                              /  \  
10   30                           10   30
                                          \   
                                          40

// C program to demonstrate insert operation in binary search tree

include #

include #

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

// A utility function to create a new BST node
struct node *newNode(int item)
{
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}

// A utility function to do inorder traversal of BST
void inorder(struct node *root)
{
if (root != NULL)
{
inorder(root->left);
printf(“%d ”, root->key);
inorder(root->right);
}
}

/* A utility function to insert a new node with given key in BST /
struct node insert(struct node* node, int key)
{
/* If the tree is empty, return a new node */
if (node == NULL) return newNode(key);

/* Otherwise, recur down the tree */
if (key < node->key)
    node->left  = insert(node->left, key);
else
    node->right = insert(node->right, key);

/* return the (unchanged) node pointer */
return node;

}

// Driver Program to test above functions
int main()
{
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
struct node *root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);

// print inoder traversal of the BST
inorder(root);

return 0;

}
Output:

20 30 40 50 60 70 80
Time Complexity: The worst case time complexity of search and insert operations is O(h) where h is height of Binary Search Tree. In worst case, we may have to travel from root to the deepest leaf node. The height of a skewed tree may become n and the time complexity of search and insert operation may become O(n).