Binary Tree Data Structure Questions

Insertion is the correct term for adding a new node to a binary tree.

An empty binary tree is simply a tree with no nodes, which is a valid state.

BST stands for Binary Search Tree, a specific type of binary tree with a special ordering property that makes searching efficient.

Binary trees find use in various domains due to their structural properties. They excel at maintaining sorted data, representing hierarchies, and serving as the foundation for efficient algorithms.

A balanced binary tree maintains a height that is close to the logarithm of the number of nodes. This balance is achieved if, for every node in the tree, the height difference between its left and right subtrees is no more than 1. Additionally, the left and right subtrees themselves must also be balanced.

In a binary tree, there is only one possible path to traverse from the root node to any other specific node within the tree structure.

While the average case for insertion is O(log n), the worst-case scenario occurs when the tree becomes skewed (resembling a linked list), requiring traversal of all existing nodes.

In a balanced binary tree, each level contains roughly twice the number of nodes as the level above it. This structure enables searching to eliminate half of the remaining nodes with each comparison, leading to a logarithmic time complexity.

The minimum height is achieved when the tree is as balanced as possible. With 5 nodes, the most balanced structure would result in a height of 2.

Deleting a node with two children requires careful handling to preserve the tree structure. Replacing it with its inorder successor (or predecessor) maintains the order of elements.

Both the smallest value in the right subtree and the largest in the left subtree maintain the ordering property of a BST.

A complete binary tree is filled at each level except possibly the last level, which is filled from left to right. This structure ensures a logarithmic relationship between the number of nodes and the height. The floor function is used because the height is always an integer.

In a binary search tree, the left subtree always contains values smaller than the root. Therefore, the leftmost node in the tree will hold the minimum value. Inorder traversal visits nodes in ascending order for a BST.

The depth of a node in a binary tree is the number of edges in the path from the root node to that specific node.

A node directly connected to another node when moving away from the root is referred to as a child.

By definition, a binary tree node can have at most two children, often referred to as the left child and the right child.

Insertions usually happen at leaf nodes to maintain the tree structure. The specific leaf node chosen often depends on the insertion algorithm and the data being inserted.

In a complete binary tree, each level 'l' can have a maximum of 2 raised to the power of 'l' nodes. This is because each level doubles the number of nodes from the previous level.

The size of a binary tree is the total number of nodes it contains. A tree with only a root node has a size of 1.

Both stacks (iterative inorder traversal) and queues (level-order traversal with range checks) can be used to validate BST properties.