Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Data Structures > Trees, Binary Trees, BSTs > Flashcards

Trees, Binary Trees, BSTs Flashcards

1
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

The depth of a node x is also its…

A

level in the tree

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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

A

depth

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is the height of a node x

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is the height of any leaf node?

A

0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is the height of a tree?

A

Height of root node

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is the only requirement for a binary tree

A

All nodes can have at most two children

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is a full binary tree?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is a complete binary tree?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

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

A

2^h where h is the height of the root

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is a perfect binary tree?

A

A binary tree where all levels are completely filled

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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

A

True

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

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

A

h = log_2(n+1) - 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

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 _____

A

tree height. h, height

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is the minimum possible height in a BST?

A

h = floor of log_2(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

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

A

h = n

19
Q

How do you know if a binary tree is balanced?

A

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)

20
Q

What is the height of a leaf node?

A

0

21
Q

What is the height of an empty tree?

A

-1

22
Q

How do you determine the balance factor of a node?

A

height of right subtree - height of left subtree

23
Q

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

A

positive number greater than 1

24
Q

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

A

negative number less than -1

25
Q

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

A

0

26
Q

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

A

All of them are O(log n)

27
Q

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

A

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

28
Q

What are the properties required for a BST?

A

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

29
Q

Pseudocode for finding height of a tree

A

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

30
Q

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

A

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

31
Q

Explain depth first traversal

A

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

32
Q

What are the three types of depth first traversal?

A
  1. pre-order traversal
  2. in-order traversal
  3. post-order traversal
33
Q

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

A

Root, left subtree, right subtree

34
Q

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

A

Left subtree, root, right subtree

35
Q

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

A

Left subtree, right subtree, root

36
Q

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

A

in order traversal

37
Q

What is the time complexity of level order traversal?

A

O(n)

38
Q

What’s the pseudocode for level order traversal?

A

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)

39
Q

Whats the pseudocode for pre-order traversal?

A

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

40
Q

What is the pseudocode for in-order traversal?

A

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

41
Q

What is the pseudocode for post-order traversal?

A

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

42
Q

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

A

Case 1: Leaf node or node with no children

Case 2: Node with one child

Case 3: Node with three children

43
Q

Inserted elements into a BST are always inserted as ______

A

leaves

Data Structures (5 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions