Binary Search Tree

Question 1

Three rules of binary search tree

Answer 1

1. Each node can have up to two children: a left child, a right child, both, or neither. Each child is a node as well, and is the root of its corresponding subtree (e.g., the root’s left child is the root of the left subtree).
2. The values of each node in the left subtree must be less than the value of the root.
3. The values of each node in the right subtree must be greater than the value of the root.

Question 2

Describe steps to insert an element into the tree

Answer 2

Compare value to root to decide into which side of the tree value should be inserted.
If value > root, check for root’s right child. If root has a right child, perform insert(value, root.right_child). Otherwise, make value into root’s right child.
If value < root, check for root’s left child. If root has a left child, perform insert(value, root.left_child). Otherwise, make value into root’s left child.

Question 3

How do you delete a node with both left and right children?

Answer 3

Find a replacement by going through the left child then finding the maximum element
https://github.com/appacademy/sf-job-search-curriculum/blob/master/algorithms/binary_search_trees/bst_reading.md

Question 4

In order binary tree traversal

Answer 4

Visit(print) the left branch, then current node, then right branch

Question 5

Pre order traversal of binary tree

Answer 5

Visit current node before child nodes

Question 6

Post order traversal binary tree

Answer 6

Visit current node after visiting child nodes