The three properties describing a binary search tree are wrong! It isn’t just about a node and its two children. It’s about a node and its descendants. The properties should read:

- All descendants down the left edge of a node must have a value less than the node’s value.
- All descendants down the right edge of a node must have a value greater than the node’s value.
- These two properties hold for all nodes in the tree.

Don’t the “node-scope” rules described in the article imply the “tree-scope” phenomenon you’re describing?

The platform could have an option to favorite some topics.

Isn’t the image in the definition incorrect? 2 is less than 6 and is placed on the left branch of the node so it is a valid binary search tree?

I dont understand the return tree

2 is less than six so it is correct to have it in the left subtree of 6, BUT 2 is also less than 3, so it should also be in the left subtree of 3. The correct location for 2 is shown below:

8

/

3 10

/

1 6

2

Didn’t realize the comment would clobber my spacing and mess up my beautiful tree ASCII drawing. 2 should be the RIGHT CHILD of 1, that way 1 and 2 are both in the left subtree below 3 and 2 is in the right subtree below 1 (since 2 is greater than one but less than 3). Here’s the correct BST in algo monsters format:

8 3 1 x 2 x x 6 x x 10 x x

Can you explain return tree line more?

def insert(tree, val):

if tree is None:

return Node(val)

if tree.val < val:

tree.right = insert(tree.right, val)

elif tree.val > val:

tree.left = insert(tree.left, val)

return tree

Very nice the end section comparing BSTs with sorted arrays and hash tables