Insertion in binary search tree

In binary search tree (BST), Nodes are inserted in sorted order (inorder sequence is always sorted). Every node of this tree, contains a key. This key indicates where the new node will be added. There is following point which is useful to understand BST properties.

1) First inserted node is called root node.

2) Every node can be hold 2 child node. Which is called left and right child or called left and right subtree.

3) Which contains at least one child is called parent node.

4) When node not contain any child nodes this is called leaf node.

5) Node key of left subtree can be less than or equal to every parent node key.

6) Node key of right subtree always be greater than or equal to every parent node key.

5th and 6th point is very important to implement algorithm. Try to understand its with this example.

Insertion in binary search tree

There is two main techniques are used to add a new node.

A) Iterative implementation

B) Recursive implementation



Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved