How do integers get placed inside a search-tree structure?

Question

As far as I know small value integers are placed at LHS and a big value is placed at RHS.
Can anyone give a good explanation?

Answer 1

Just to go over the background (skip this if you know it already):

A tree is a collection of nodes connected by edge with no loops allowed. The topmost node is called the root node. Nodes can have zero or more child nodes, which are nodes that extend downward from it. All nodes have exactly one parent node that extends upward from it (the root is the exception and has not parents). Allowing more than one parent would create loops, which are not allowed in trees.

A binary tree is a special type of tree where every node has at most two child nodes. All nodes in a binary tree have a value, a left pointer and a right pointer. The pointers point to the left and right child nodes, if they exist. If they don't exist, the pointers are NULL pointers don't point anywhere.

A binary search tree is a special type binary tree where the nodes are organized in a special way:

• given any node, all nodes in its left subtree will have a lesser value
• given any node, all nodes in its right subtree will have a greater value

Binary search trees are organized like this to allow for easy searching of values.

Now for the insertion algorithm...

Let's say we are given the number 3 to insert into the following tree:

     6
   /   \
  4     9
 / \   /
2   5 8

All we need to do is start at the root and descend down the tree, going left if our new value less than the node value, and right if the our new value is greater. We stop when we find an empty space to insert out node.

So to insert the number 3...

• start at the top node
• 3 is less than 6, so go left
• 3 is less than 4, so go left
• 3 is greater than 2, so go right
• we've found empty space for a new node, so insert it here

      6
    /   \
   4     9
  / \   /
 2   5 8
  \
   3

The Insert() procedure can be defined recursively. Once we decide to move left or right, we can just focus on the subtree below the current node and forget about the rest of the tree.

In pseudocode:

Insert(Node root, int newValue)
    if (root is empty)
        Node N = new Node
        N.value = newValue
    else if (root.value < newValue)
        Insert(root.left, newValue)
    else if (root.value > newValue)
        Insert(root.left, newValue)