07 Trees and Binary Search Trees Free Online FlashCards

What is a tree in data structures?

A tree is a hierarchical structure of nodes connected by edges with no cycles; there is exactly one path between the root and any other node.

How do depth and height differ in a tree?

A node’s depth is its number of edges from the root. A node’s height is the number of edges on its longest downward path to a leaf.

What defines a binary tree?

A binary tree is a tree in which each node has at most two children, designated as its left and right subtrees.

What is a full binary tree?

In a full binary tree, every node has either zero children or two children.

What is a complete binary tree?

A complete binary tree has every level full except possibly the last, and its last level is filled from left to right.

What is the preorder sequence for the example tree?

Preorder visits the root, then the left subtree, then the right subtree. For the example tree, the sequence is A, B, D, E, C, F.

Why is inorder traversal important for a BST?

Inorder traversal visits the left subtree, the node, then the right subtree. In a BST, this produces keys in ascending order.

When is postorder traversal especially useful?

Postorder visits the left subtree, the right subtree, and then the node. It is useful when descendants must be processed before their parent, such as freeing nodes.

How does level-order traversal visit nodes?

Level-order traversal visits nodes one level at a time from top to bottom, usually left to right, and is commonly implemented with a queue.

What ordering property defines a BST?

For each node with key K, every key in its left subtree is smaller than K and every key in its right subtree is larger, under the stated duplicate policy.

What path finds 7 in the example BST?

The search path is 8 → 3 → 6 → 7. Each comparison selects the left or right subtree that could contain the target.

Where is 5 inserted in the example BST?

Inserting 5 follows 8 → 3 → 6 → 4; because 5 is greater than 4, it becomes the right child of 4.