A binary tree node contains three fields: pseudocode class TreeNode: val: integer left: TreeNode or null right: TreeNode or null The left and right pointers reference child nodes. A node with no children is called a leaf.
The topmost node is the root.
Terminology:
- Depth: distance from root (root has depth 0)
- Height: maximum depth of any leaf in the subtree
- Complete tree: every level filled except possibly the last, which fills left to right
- Full tree: every node has 0 or 2 children
- Perfect tree: all leaves at same depth, all internal nodes have 2 children
A perfect tree with height has nodes. Time: . Space: .