BST Pt. 1

What is a binary tree?

A data structure in which each node stores data and has up to two children.

What is a leaf in a binary tree?

A tree node with no children.

Define an internal node.

A node with at least one child.

What is the root of a binary tree?

The one tree node with no parent.

What is the depth of a node?

The number of edges on the path from the root to the node.

What is the height of a tree?

The largest depth of any node in the tree.

What defines a full binary tree?

Every node contains 0 or 2 children.

What is a complete binary tree?

All levels, except possibly the last, contain all possible nodes, and all nodes in the last level are as far left as possible.

Define a perfect binary tree.

All internal nodes have 2 children and all leaf nodes are at the same level.

What is a subtree?

Any node in the tree and all of its descendants.

What is a binary search tree (BST)?

A binary tree where each node's key is greater than all keys in the left subtree and less than all keys in the right subtree.

What is the search operation in a BST?

It returns the first node with a matching key or null if no match is found.

What is the runtime complexity of searching in a BST?

O(H), where H is the height of the tree.

What is the minimum height of a binary tree with N nodes?

log2(N).

What is the BSTNode class?

It represents a node in a binary search tree with fields for key, left child, and right child.

What does the BinarySearchTree class represent?

It represents a binary search tree with a reference to the root node.

What is the insert operation in a BST?

It inserts a new node in a proper location while obeying the BST ordering property.

What is the complexity of the insert-node operation?

Best case O(log2(N), worst case O(N).

What is a node's successor in a BST?

The node that comes after it in the BST ordering.

How do you find a node's successor if it has a right subtree?

It's the leftmost child of the right subtree.

What happens when removing a leaf node in a BST?

The parent's left or right child is assigned null.

What is the process for removing an internal node with two children?

Locate the successor, copy it to the node, and recursively remove the successor from the right subtree.

What is the purpose of the insertKey() method?

It checks if a key already exists and inserts a new node if it does not.

What is the runtime complexity of the insertKey() method?

Best case O(log2(N), worst case O(N)..

What defines a balanced BST?

The height difference between the left and right subtrees of every node is no more than 1.

What is the search runtime complexity in a balanced BST?

O(log N).

What is the significance of the BST structure for search operations?

It enables much faster search, insert, and remove operations compared to a linked list.