CODEWITHSUNDEEP
binary-search-tree
LOCKLOCK
LOCKLOCK

Reputation: 351

Binary Search Tree Minimum Value

I am new to binary search tree data structure. One thing I don't understand is why the leftest node is the smallest

      10
    /    \
   5      12  
  / \    /  \     
 1   6  0   14

In the above instance, 0 is the smallest value not 1.

Let me know where I got mixed up.

Thank you!

Upvotes: 1

Views: 275

Answers (3)

Maxfield Chandler
Maxfield Chandler

Reputation: 43

I'm not really sure of your question, but binary search works by comparing the search-value to the value of the node, starting with the root node (value 10 here). If the search-value is less, it then looks at the left node of the root (value 5), otherwise it looks next at the right node (12).

It doesn't matter so much where in the tree the value is as long as the less and greater rule is followed.

In fact, you want to have trees set up like this (except for the bad 0 node), because the more balanced a tree is (number of nodes on left vs. number of nodes on right), the faster your search will be!

A tree balancing algorithm might, for example, look for the median value in a list of values and make that the value of the root node.

Upvotes: 1

Vic
Vic

Reputation: 8971

For a tree to be considered as a binary search tree, it must satisfy the following property:

... the key in each node must be greater than all keys stored in the left sub-tree, and smaller than all keys in right sub-tree

Source: https://en.wikipedia.org/wiki/Binary_search_tree

The tree you posted is not a binary search tree because the root node (10) is not smaller than all keys in the right sub-tree (node 0)

Upvotes: 1

OmerFaruk
OmerFaruk

Reputation: 292

That tree is not binary search tree.

Creating a binary search tree is a process which starts with adding elements.

You can do it with array.

First there is no element so make it root.Then start adding elements as node.If the new value is bigger than before add it array[2 x n + 1] (call index of the last value: n). If it is smaller than before add it to array[2 x n]. So all values left of any node is smaller than it and all values right of any node is bigger than it. Even 10 and 6's place.6 cannot be 11.(at your tree,it isn't actually.).That's all !

Upvotes: 1

Related Questions