How to add add node in binary tree

Question

                   (5)Root
          (3)-------^--------(7)
     (2)---^----(5)           ^-----(8)

i want to add node with data 5 in this binray tree....Please help.....i really stuck in it

Answer 1

You traverse the binary tree from the root:

• if your new element is less or equal than the current node, you go to the left subtree, otherwise to the right subtree and continue traversing

• if you arrived at a node, where you can not go any deeper, because there is no subtree, this is the place to insert your new element

                 (5)Root
        (3)-------^--------(7)
   (2)---^----(5)           ^-----(8)
          (5)--^
  

You start at (5), then go left (since 5 <= 5) to (3), then go right (since 5 > 3) to (5), then you want to go to the left subtree (since 5 <= 5), but you see that there is no subtree, so this is the place to insert your new element (5).

Answer 2

It depends on whether you want to keep your binary tree:

• sorted
• balanced

If neither of these are requirements then the fastest way to add an element is to put it as the new root and have the rest of the tree has one of its children:

                         (5)
                   (5)----^
          (3)-------^--------(7)
     (2)---^----(5)           ^-----(8)

For binary search trees you should not have repeated values and the process for insertion is more complicated and requires traversing the tree to find the insertion point. See here.

For self-balancing binary search trees it is even more complicated and can for example involve performing tree rotations. See here for more details.