Trees, Binary Trees, BSTs

Question 1

What is the “depth” of a node x. Depth is always relative to…

Answer 1

Length of path from the root of the TREE to that node. Depth is always relative to the root of the tree

Question 2

The depth of a node x is also its…

Answer 2

level in the tree

Question 3

Siblings or cousins of a tree have the same…(starts with a d)

Answer 3

depth

Question 4

What is the height of a node x

Answer 4

Height of any node x in a tree is the number of edges of the longest path from that node to a leaf node.

Question 5

What is the height of any leaf node?

Answer 5

0

Question 6

What is the height of a tree?

Answer 6

Height of root node

Question 7

What is the only requirement for a binary tree

Answer 7

All nodes can have at most two children

Question 8

What is a full binary tree?

Answer 8

a binary tree in which every node has two or zero children Another definition is: a binary tree in which every interior node has exactly two children

Question 9

What is a complete binary tree?

Answer 9

A binary tree where all levels except possibly the last level are completely filled and as far left as possible

Question 10

What is the max number of leaves you can have in a complete binary tree?

Answer 10

2^h where h is the height of the root

Question 11

What is a perfect binary tree?

Answer 11

A binary tree where all levels are completely filled

Question 12

True or false: a perfect binary tree is also a complete tree

Answer 12

True

Question 13

How many nodes are there in a perfect tree with height h?

Answer 13

2^(h+1)-1 or 2^(levels in the tree) - 1

Question 14

What is the height of a perfect binary tree with n nodes?

Answer 14

h = log_2(n+1) - 1

Question 15

What is the equation for the height of a complete binary tree?

Answer 15

floor of log_2(n) where n = # of nodes

Question 16

Time complexity of inserting, searching, and removing an element is proportional to its _____ in a BST. Thus, time complexity can be said to be O of ______ in terms of the tree’s _____

Answer 16

tree height. h, height

Question 17

What is the minimum possible height in a BST?

Answer 17

h = floor of log_2(n)

Question 18

What is the maximum worst case possible height in a BST?

Answer 18

h = n

Question 19

How do you know if a binary tree is balanced?

Answer 19

A binary tree is balanced if for EACH node the difference of the left and right subtree is not more than some number k (usually 1)

Question 20

What is the height of a leaf node?

Answer 20

0

Question 21

What is the height of an empty tree?

Answer 21

-1

Question 22

How do you determine the balance factor of a node?

Answer 22

height of right subtree - height of left subtree

Question 23

What is the value you get when a node is right heavy?

Answer 23

positive number greater than 1

Question 24

What is the value you get when a node is left heavy?

Answer 24

negative number less than -1

Question 25

What is the value you get when a node is evenly balanced?

Answer 25

0

Question 26

What is the time complexity of search, insertion, and removal in AVERAGE case in a BST?

Answer 26

All of them are O(log n)

Question 27

What is the WORST CASE time complexity of search, insertion, and removal in a BST? What would a BST look like in this case?

Answer 27

O(n). BST would like like a linked list

Question 28

What are the properties required for a BST?

Answer 28

Nodes can have at most 2 children Values in the right subtree/child are greater than or equal to the root node values in the left subtree/child are less than the root node value

Question 29

Pseudocode for finding height of a tree

Answer 29

find\_height(root): if root is None: return - 1 left\_height = find\_height(root.left) right\_height = find\_height(root.right) return max(left\_height, right\_height) + 1

Question 30

What is breadth first/level-order traversal? traversal in a binary tree?

Answer 30

Breadth first visits every node from left to right, level by level.

Question 31

Explain depth first traversal

Answer 31

Depth first visits the depth of one subtree before the other subtree

Question 32

What are the three types of depth first traversal?

Answer 32

1. pre-order traversal 2. in-order traversal 3. post-order traversal

Question 33

Explain pre-order traversal. What's the order of processing data?

Answer 33

Root, left subtree, right subtree

Question 34

Explain in-order traversal. What's the order of processing data?

Answer 34

Left subtree, root, right subtree

Question 35

Explain post-order traversal. What's the order of processing data?

Answer 35

Left subtree, right subtree, root

Question 36

Which traversal method gives you a sorted order of the values of the binary search tree?

Answer 36

in order traversal

Question 37

What is the time complexity of level order traversal?

Answer 37

O(n)

Question 38

What's the pseudocode for level order traversal?

Answer 38

queue() queue.push(root\_of\_tree) while queue is not empty: curent\_node = queue.pop() if current\_node.left\_child is not none: queue.push(left\_child) if current\_noderight\_child is not none: queue.push(right\_child)

Question 39

Whats the pseudocode for pre-order traversal?

Answer 39

DynamicArray() # for storing the values we visit def pre\_order\_trav(current\_node, dynamic\_array): if current\_node: dynamic\_array.push(current\_node.data) self. pre\_order\_trav(current\_node.left) self. pre\_order\_trav(current\_node.right) return dynamic\_array

Question 40

What is the pseudocode for in-order traversal?

Answer 40

DynamicArray() # for storing the values we visit def in\_order\_trav(current\_node, dynamic\_array): if current\_node: self.in\_order\_trav(current\_node.left) dynamic\_array.push(current\_node.data) self.in\_order\_trav(current\_node.right) return dynamic\_array

Question 41

What is the pseudocode for post-order traversal?

Answer 41

DynamicArray() # for storing the values we visit def post\_order\_trav(current\_node, dynamic\_array): if current\_node: self. pre\_order\_trav(current\_node.left) self. pre\_order\_trav(current\_node.right) dynamic\_array.push(current\_node.data) return dynamic\_array

Question 42

What are the three cases to consider when removing a node from a BST?

Answer 42

Case 1: Leaf node or node with no children Case 2: Node with one child Case 3: Node with three children

Question 43

Inserted elements into a BST are always inserted as \_\_\_\_\_\_

Answer 43

leaves