Trees

Question 1

Explain binary trees

Answer 1

In general, nodes in trees can have any number of children. However, for binary trees every node has two or fewer children. The number of children each node has in a tree is called the branching factor, and each node has exactly one parent. The branching factor for a binary tree is 2.

Question 2

What are leaves?

Answer 2

Nodes pointing to no other nodes are called leaves.

Question 3

What is the depth of a node?

Answer 3

Nodes pointing to no other nodes are called leaves.

Question 4

What is the node height?

Answer 4

The node height is the number of nodes from between the original node and the deepest leaf that is a descendent.

Question 5

What is the tree height?

Answer 5

The tree height is the node height of the root, i.e. the number of branches along the longest path in the tree.

Question 6

What is the largest number of nodes a binary tree can have that has a tree height of 5?

Answer 6

2n - 1 // n being 6 because of including the root node

Question 7

What is a full binary tree?

Answer 7

A full binary tree is a binary tree in which each node has exactly zero or two children.

Question 8

What is a complete tree?

Answer 8

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

Question 9

What is a traversal?

Answer 9

so that you can navigate the tree and find all the data it contains. This is known as a traversal, since it traverses the whole binary tree.

Question 10

What is the code for a pre-order traversal?

Answer 10

def traverse(tree):
    if tree:
        print(tree.getRootVal())
        traverse(tree.getLeftChild())
        traverse(tree.getRightChild())

Question 11

What is the code for an in-order traversal?

Answer 11

def traverse(tree):
    if tree:
        traverse(tree.getLeftChild())
        print(tree.getRootVal())
        traverse(tree.getRightChild())

Question 12

What is the code for a post-order traversal?

Answer 12

def traverse(tree):
    if tree:
        traverse(tree.getLeftChild())
        traverse(tree.getRightChild())
        print(tree.getRootVal())

Question 13

What is DFS?

Answer 13

DFS, is the strategy that goes down a branch all the way until a leaf is reached, processes said branch, and then moves on to a different branch.

Question 14

Is the depth-first search always the way to go? For what cases might there be a better solution?

How about if you would like to see how many connections there are between you and another person on Facebook?

Answer 14

BFS, is the counterpart to DFS in tree traversing techniques. It is a search algorithm that traverses down a tree using a queue as its data array, where elements are visited in a FIFO, first-in first-out, mechanism.

Question 15

How is BFS often used?

Answer 15

This type of search is often used when looking for the “nearest” solution.

Question 16

What is another example of BFS?

Answer 16

finding the shortest route from point A to point B (e.g. directions from “Google Maps”)

Question 17

As we’ve seen, binary trees can be used for storing data; however, how can we store data in a binary tree in a useful manner, i.e. so that we can find and look up data efficiently?

Answer 17

In a BST, for any parent (including the root) all elements in any left sub-tree must be smaller than the parent, and all elements in any right sub-tree must be larger than any element in the left sub-tree.

Question 18

Which of the following trees will have a better worst case runtime?

A balanced BST with a depth of 20
An unbalanced BST with a depth of 18

Answer 18

Although the second one is unbalanced, the number of comparisons needed will be determined by the depth of the tree. (Worst case, it traverses all the way to the bottom of the tree.) Since B has a smaller depth than A, it will have a better worst case runtime.

Question 19

What is a tree rotation?

Answer 19

A tree rotation is an operation on a binary tree that changes the structure of the tree without affecting the order of the elements (as read in by an in-order traversal).

Question 20

What do tree rotations do?

Answer 20

Tree rotations change the height of the tree by moving up larger subtrees.

Question 21

What is an AVL tree?

Answer 21

An AVL tree, named after its inventors, Adelson-Velskii and Landis, is a self-balancing BST that applies a tree rotation automatically.