(5)Root (3)-------^--------(7) (2)---^----(5) ^-----(8)
I want to add node with data 5 in this binary Search tree. Please help.
4 Answers
Note: This answer assumes you are talking about a binary search tree.
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).
3 Comments
Brian Ogden
So the OP did say it was a Binary Tree, you have provided an answer that is more or less for a Binary Search Tree though you would not allow a duplicate 5 to be added to a Binary Search Tree
phimuemue
@Saurabh I guess it depends on your definition, and for certain situations it is convenient to disallow duplicate values, while others are fine with them. The question seems seek for explanations on the basic concepts of a binary tree, so I thought that covering (one way of) how to deal with duplicate elements makes sense here.
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.
Comments
private void Insert(Node node, ref Node tree)
{
if (tree == null) // Found a leaf?
{
tree = node; // Found it! Add the new node as the new leaf.
}
else
{
int val = string.Compare(node.Key, tree.Key); // already inserted
if (val == 0)
{
throw new InvalidOperationException("Duplicate key");
}
elseif (val < 0)
{
Node left = tree.Left;
Insert(node, ref left); // Keep moving down the left side.
tree.Left = left;
}
else
{
Node right = tree.Right;
Insert(node, ref right); // Keep moving down the right side.
tree.Right = right;
}
}
}
Comments
/// <summary>
/// Construct the tree from a pre order traversal
/// </summary>
/// <param name="preorderTraversal"></param>
/// <returns></returns>
public static TreeNode ConstructTreeFromPreOrderTraversal(int[] preorderTraversal)
{
if (null == preorderTraversal || preorderTraversal.Length < 1)
return null;
TreeNode root = null;
int len = preorderTraversal.Length;
for (int i = 0; i < len; i++)
{
TreeNode newNode = new TreeNode();
newNode.Data = preorderTraversal[i];
newNode.Left = newNode.Right = null;
AddNode(ref root, newNode);
}
return root;
}
/// <summary>
/// add not in the tree
/// </summary>
/// <param name="root"></param>
/// <param name="newNode"></param>
private static void AddNode(ref TreeNode root, TreeNode newNode)
{
if (root == null)
root = newNode;
else if (newNode.Data < root.Data)
{
TreeNode left = root.Left;
AddNode(ref left, newNode);
root.Left = left;
}
else
{
TreeNode right = root.Right;
AddNode(ref right, newNode);
root.Right = right;
}
}
5s?