CODEWITHSUNDEEP
algorithmbinary-search-tree
user23475
user23475

Reputation: 1

BST element ordering

In a BST (binary search tree), can any element to the right of the root node be smaller than the root node?

Ie, root is 4, right child is 10, then the left child of that right child is -234

Is it possible/allowed in the definition?

Upvotes: 0

Views: 168

Answers (1)

Yola
Yola

Reputation: 19021

No. See Binary search tree

A binary search tree is a rooted binary tree, whose internal nodes each store a key (and optionally, an associated value) and each have two distinguished sub-trees, commonly denoted left and right. The tree additionally satisfies the binary search property, which states that the key in each node must be greater than or equal to any key stored in the left sub-tree, and less than or equal to any key stored in the right sub-tree.

When you arrive at some, say it contains value 4, and you want to find node with value -234, you always go to the left and if you want to find a node with value 10 you always go to the right.

Upvotes: 2

Related Questions