Binary search trees node sizes

1
votes

I'm slightly confused about how the order of nodes can be arranged in a binary search tree. Can there be node of a subtree in a binary search tree on the left that is larger than the root node?

For example, would the following be a binary search tree?

    2
   / \
  1   4
 / \
    3

What confuses me above is whether or not the right subtree of the 1 (3) can be larger than the original root node (2).

1
binary-search-tree

1 Answers

3
votes

No, there cannot be nodes to the left that are larger than the root. A binary search tree has the following properties (from wiki):

  1. The left subtree of a node contains only nodes with keys less than the node's key.
  2. The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
  3. Both the left and right subtrees must also be binary search trees.