Binary Trees Flashcards
What is a binary tree?
A binary tree is a tree data structure where each node has at most two children, typically referred to as the left child and the right child.
What is a node in a binary tree?
A node is a fundamental part of a binary tree that stores data and has pointers to its left and right children (if they exist).
What are parent and child nodes in a binary tree?
A parent node has references to one or two child nodes, while child nodes are those connected directly below a parent node.
What is the maximum height of a binary tree with N nodes?
The maximum height occurs when the tree is skewed (like a linked list), and the height is Nā1.
What are the invariants of a binary search tree (BST)?
In a BST:
The left subtree contains only nodes with values less than the parent node.
The right subtree contains only nodes with values greater than the parent node.
Both left and right subtrees must also be binary search trees.
How many children does a non-leaf node have in a binary tree?
A non-leaf node in a binary tree has one or two children.
How many parents does a non-root node have in a binary tree?
A non-root node has exactly one parent.
What makes a binary tree balanced?
A binary tree is balanced if the heights of the left and right subtrees of any node differ by at most 1.
What makes a binary tree unbalanced?
A binary tree is unbalanced if one subtree is significantly deeper than the other, leading to inefficient operations.
What is in-order traversal of a binary tree?
In-order traversal visits the left subtree, the root, and then the right subtree.
Example: For a BST with nodes 2, 1, 3:
In-order traversal: 1, 2, 3
What is pre-order traversal of a binary tree?
Pre-order traversal visits the root first, then the left subtree, followed by the right subtree.
Example: For the same BST (2, 1, 3):
Pre-order traversal: 2, 1, 3
What is post-order traversal of a binary tree?
Post-order traversal visits the left subtree, then the right subtree, and finally the root.
Example: For the BST (2, 1, 3):
Post-order traversal: 1, 3, 2
What is an expression tree?
An expression tree is a binary tree where the internal nodes represent operators, and the leaf nodes represent operands.
What are the properties of an expression tree?
Operands are at the leaf nodes.
Operators are at internal nodes.
The tree follows the order of operations.
What is the worst-case time complexity for insertion in a BST?
The worst-case time complexity is
O(N), occurring when the tree becomes unbalanced.
