final exam eeek! Flashcards
What is the relationship between elements in a tree called?
Edge or arc
The height of a tree?
the maximum depth of any node in the tree
The depth of a node in a tree?
the length of the path from the root to the node
True/False
Each node in the structure may have only one parent
True
Edges in a tree can’t create cycles meaning…
a path from the node can’t lead back to itself
A binary tree is different from a normal tree how?
Each node can only have at most 2 children
The three types of binary trees are
perfect, complete, and full
What is a full binary tree?
Every node has exactly two child nodes or zero child nodes
What is a perfect binary tree?
a full binary tree where all the leaves are at the same depth
In a perfect binary tree, if we know height is h, how many leaves does it have?
2^h
In a perfect binary tree, if we know height is h, how many nodes does it have?
(2^(h+1)) - 1
In a perfect binary tree, if we know the tree has n nodes, what is the height?
log(n)
What is a complete binary tree?
binary tree that is perfect except for the deepest level, where all the nodes are all as far left as possible
What is the binary search tree property?
Within a binary search tree, the key of each node N is greater than all the keys in N’s left subtree and less than or equal to all the keys in N’s right subtree
What is a depth-first traversal?
visits descendants before siblings –> moves as far downwards as it can first before going sideways
