A binary tree node contains three fields: 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.
Key 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: .