Trees Flashcards
What is an Internal Node?
A node with at least one child.
What is a Leaf/External Node?
A node with no children.
What is an Ancestor of a Node?
parent, grandparent, etc of a node.
What is the height of a Node?
Maximum number of nodes needed to be
traversed to reach a leaf node. In this class, the
height of a leaf node is 0.
What is the depth of a Node?
Number of nodes needed to be traversed to reach
the root node. In this class, the depth of the root
node is 1 (which means the depth of the root node’s
children is 2).
What is a Binary Tree?
A binary tree is a special case of a tree where each node has at most two children (a left child and a right child).
What is a Binary Search Tree?
A binary search tree is a special case of a binary tree where the left child of a node is smaller than the current node and the right child of a node is larger than the current node (where equal items go is implementation-defined).
What is a Tree Traversal?
A traversal visits the nodes of a tree in a systematic manner.
What Tree Traversals can you perform on a Binary Search Tree?
For all trees, you can perform a preorder traversal, postorder traversal, or a level-order traversal. For a Binary Search Tree you can also do an In-order traversal.
Describe a Pre-Order Traversal.
In a preorder traversal, a node is visited first, then the child nodes are visited (from left to right).
Describe a Post-Order Traversal.
In a postorder traversal, the child nodes are visited first (from left to right), then the node itself is visited.
What is a predecessor?
The predecessor node is the node that has the largest data, but is less than the data in the current node (in other words, the node with the largest data in the left subtree of the
current node).
What is a successor?
The successor node is the node that has the smallest data, but is greater than the data in the current node (in other words, the node with the smallest data in the right subtree of the current node).
What is the best case Big O for Inserting into a BST?
O ( log n )
What is the worst case Big O for Inserting into a BST?
O ( n )
