Trees, Binary Trees, BSTs Flashcards
What is the “depth” of a node x. Depth is always relative to…
Length of path from the root of the TREE to that node. Depth is always relative to the root of the tree
The depth of a node x is also its…
level in the tree
Siblings or cousins of a tree have the same…(starts with a d)
depth
What is the height of a node x
Height of any node x in a tree is the number of edges of the longest path from that node to a leaf node.
What is the height of any leaf node?
0
What is the height of a tree?
Height of root node
What is the only requirement for a binary tree
All nodes can have at most two children
What is a full binary tree?
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
What is a complete binary tree?
A binary tree where all levels except possibly the last level are completely filled and as far left as possible
What is the max number of leaves you can have in a complete binary tree?
2^h where h is the height of the root
What is a perfect binary tree?
A binary tree where all levels are completely filled
True or false: a perfect binary tree is also a complete tree
True
How many nodes are there in a perfect tree with height h?
2^(h+1)-1 or 2^(levels in the tree) - 1
What is the height of a perfect binary tree with n nodes?
h = log_2(n+1) - 1
What is the equation for the height of a complete binary tree?
floor of log_2(n) where n = # of nodes
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 _____
tree height. h, height
What is the minimum possible height in a BST?
h = floor of log_2(n)
What is the maximum worst case possible height in a BST?
h = n
How do you know if a binary tree is balanced?
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)
What is the height of a leaf node?
0
What is the height of an empty tree?
-1
How do you determine the balance factor of a node?
height of right subtree - height of left subtree
What is the value you get when a node is right heavy?
positive number greater than 1
What is the value you get when a node is left heavy?
negative number less than -1
What is the value you get when a node is evenly balanced?
0
What is the time complexity of search, insertion, and removal in AVERAGE case in a BST?
All of them are O(log n)
What is the WORST CASE time complexity of search, insertion, and removal in a BST? What would a BST look like in this case?
O(n). BST would like like a linked list
What are the properties required for a BST?
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
Pseudocode for finding height of a tree
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
What is breadth first/level-order traversal? traversal in a binary tree?
Breadth first visits every node from left to right, level by level.
Explain depth first traversal
Depth first visits the depth of one subtree before the other subtree
What are the three types of depth first traversal?
- pre-order traversal
- in-order traversal
- post-order traversal
Explain pre-order traversal. What’s the order of processing data?
Root, left subtree, right subtree
Explain in-order traversal. What’s the order of processing data?
Left subtree, root, right subtree
Explain post-order traversal. What’s the order of processing data?
Left subtree, right subtree, root
Which traversal method gives you a sorted order of the values of the binary search tree?
in order traversal
What is the time complexity of level order traversal?
O(n)
What’s the pseudocode for level order traversal?
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)
Whats the pseudocode for pre-order traversal?
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
What is the pseudocode for in-order traversal?
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
What is the pseudocode for post-order traversal?
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
What are the three cases to consider when removing a node from a BST?
Case 1: Leaf node or node with no children
Case 2: Node with one child
Case 3: Node with three children
Inserted elements into a BST are always inserted as ______
leaves
