How to insert a node in a binary search tree
Given a binary search tree
and an integer
, insert this value
into the binary search tree
and return the root
node.
Example
Input: 3 value = 1
/ \
2 8
Output: 3
/ \
2 8
/
1
A Binary Search Tree
(BST) is a binary tree where each node has a key and meet the following requirements:
- The
left subtree
of a node contains nodes with keyssmaller
then the node's key - The
right subtree
of a node contains nodes with keyslarger
then the node's key - The
left
andright
subtrees arebinary search trees
Algorithm
The insertion should not break the binary search tree. To find a place where to insert a new key, we traverse the binary search tree from root to leaf.
During the traversal, we compare the new value with the node value and:
- if the
new key
isgreater
the node value we go to theright
- if the
new key
isless
the node value we go to theleft
- if the node is
null
weinsert
the new node
here's the step by step example
Code
public TreeNode Insert(TreeNode root, int value)
{
if (root == null)
{
return new TreeNode(value);
}
if (root.Value > value)
{
root.Left = Insert(root.Left, value);
}
else
{
root.Right = Insert(root.Right, value);
}
return root;
}
Time complexity : O(h)
where h
is height of given binary search tree
Recent articles
Nice to read