# Binary Search Tree Intro - Depth First Search / Binary Search Tree

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