Binary Search Tree need some help understanding this observation

Revision en1, by vikalp14, 2018-08-01 22:05:57

If rules of creating BST is as follows:

The left sub-tree contains only nodes with values less than or equal to the parent node; the right sub-tree contains only nodes with values greater than the parent node.

If a node has level i, then the subtree rooted at that node should have exactly number of distinct values in the subtree. Note that it is the number of distinct values in the subtree and not the number of nodes in the subtree.

If a is the smallest value in the tree and b is the largest value, then all values from a to b must come atleast once in the tree.

I read the editorial https://www.hackerearth.com/practice/data-structures/trees/binary-search-tree/practice-problems/algorithm/monk-and-bst/editorial/

It says that we can observe that, in subtree with N nodes, (N-1)/2 nodes will occur twice and 1 node will occur exactly once, which will be of maximum value, and tree will be of form: /predownloaded/b5/6b/b56bd180223cb9f4c840479b5a462df338b90a2b.png

Can someone explain why is this so, or better yet point me to some resource which will help me understand this.

Tags binary search tree

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English vikalp14 2018-08-01 22:07:33 69
en1 English vikalp14 2018-08-01 22:05:57 1167 Initial revision (published)