What rule to obey while inserting node into the binary tree?

Question

I know that in Binary Search Tree the elements are inserted based on there properties of inequality i.e:

 if(n->val > val) insert(n->left, val);  // root node greater then val insert to left 
 else if(n->val < val) insert(n->right, val);  // root node less then val insert to left 

 // I am ignoring the case when n->val == val here

I was curious on what basis should I insert the node into the pure (vanilla) binary tree, if there is one or do all the binary tree come with some extra property (binary search tree with its inequalities).

Are you asking where to put the value if the tree is empty? Alternatively, use std::set and let it do the insertions for you. — evan
– evan, Commented Jul 23, 2016 at 19:18
@evan Well if the tree is empty you place on the root node. So in the next insertion how to know if you should place on the right of the node or to the left. — pokche
– pokche, Commented Jul 23, 2016 at 19:22
Most implementations I've seen would place the next value to the left if it is less than and on the right if it is greater than, but it doesn't really matter as long as it's done the same way for every insertion. — evan
– evan, Commented Jul 23, 2016 at 19:27

Nikita · Accepted Answer · 2016-07-23 20:47:48Z

1

General binary tree is made of nodes, where each node contains a "left" reference, a "right" reference, and a data element. The topmost node in the tree is called the root. There are no other restrictions on data order.

But there are many types of binary trees. In literature you can see full, complete, balanced and some other. All of them has it's own rules for the tree structure. For example a full binary tree is a tree in which every node other than the leaves has two children. A balanced binary tree has the minimum possible maximum height for the leaf nodes. These specific tree types introduces extra property.

edited Jul 23, 2016 at 20:47

answered Jul 23, 2016 at 19:23

Nikita

6,4472 gold badges28 silver badges42 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

pokche Over a year ago

Yeah I know that .. but thats in the case of binary search tree

Nikita Over a year ago

@pokche good explanation of BT insert operation can be found here. Look at Insert() section.

Nikita Over a year ago

@pokche I hope my updated answer will help you better

Collectives™ on Stack Overflow

What rule to obey while inserting node into the binary tree?

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related