Binary Trees

Question 1

Difference between Binary Trees and Binary Search Trees

Answer 1

Binary Search Trees (BST) are a variation of binary trees with a sorted property to them. The property tells us that every left child must be smaller than its parent and every right child must be greater than its parent. BSTs do not allow duplicates.

Question 2

What advantages does a Binary Search Tree (BST) have over arrays?

Answer 2

Both can search in O(logn), but BSTs can add/del in O(logn) (for balanced trees) vs O(n) for arrays. If unbalanced, O(n).

Question 3

How is BST search implemented

Answer 3

Best done using recursion. You could traverse iteratively, however, that requires maintaining a stack, which is a lot more complicated.

Question 4

How are BST insert/delete implemented?

Answer 4

For insert, traverse the tree to the correct spot and insert it.
For delete, if there is one child, replace the deleted node with the child. If two children, replace the node with the lesser child. Insert and delete are O(logn) for balanced trees, but can be O(n) in the worst unbalanced case.

Question 5

Depth First Search (DFS)

Answer 5

This search method does to the bottom of the tree first. Best implemented with recursion. Three methods can be used:

Preorder - Visits parent, left child, right child
Inorder - Visits left child, parent, right child (sorted order)
Postorder - Visits left child, right child, parent.

Runs in O(n) because it visits every node in the tree

Question 6

Breadth First Search (BFS)

Answer 6

Best implemented iteratively. Uses a deque. Adds all the nodes at each level to the deque, processes them, then adds all of the next level. O(n)