6 Trees and Binary Search Trees Free Online FlashCards

What is a tree?

A tree is a hierarchical, acyclic data structure made of nodes connected by edges, accessed from a distinguished root.

What is a node's depth?

A node's depth is the number of edges from the root to that node. With root depth 0, node D has depth 2 in the example tree.

What defines a binary tree?

A binary tree is a tree in which each node has at most two children, conventionally called the left child and right child.

What is a full binary tree?

A full binary tree has either zero children or exactly two children at every node.

How many nodes are in a perfect tree of height $h$?

A perfect binary tree of height $h$ has exactly $2^{h+1}-1$ nodes.

What is preorder traversal order?

Preorder visits the current node, then the left subtree, then the right subtree: node-left-right.

Why is inorder traversal useful for a BST?

For a binary search tree, inorder traversal visits keys in sorted order because it processes left subtree, node, then right subtree.

How does level-order traversal process nodes?

Level-order traversal processes nodes by increasing depth, typically using a queue.

What is the base case for recursive node counting?

The recursive node-counting algorithm returns $0$ for an empty subtree and otherwise returns $1+count(left)+count(right)$.

What is unordered binary-tree search complexity?

Searching an unordered binary tree has worst-case time complexity $O(n)$, because both subtrees may need to be examined.

What ordering rule defines a BST?

A BST requires every key in the left subtree to be less than the node's key and every key in the right subtree to be greater.

What is the time complexity of BST search?

BST search takes $O(h)$, where $h$ is tree height, because each comparison follows only one child.