Section 10.2 Binary Trees Definitions and Properties
A binary tree is a collection of nodes, with either no elements (empty tree) or a root node and two disjoint binary subtrees, known as the left and right subtrees. The root’s children are the roots of these subtrees, and an edge connects a node to each of its children. The node is considered the parent, and the children are its direct descendants.
A sequence of nodes, n1, n2, ..., nk, where ni is the parent of ni+1 for 1≤i less than k, is called a path from n1 to nk. The length of the path is k-1. If there exists a path from node R to node M, R is referred to as the ancestor of M, and M is the descendant of R. Hence, all nodes in the tree are descendants of the root, and the root is the ancestor of all nodes.
The depth of a node M in the tree is the length of the path from the root to M. The height of a tree corresponds to the depth of its deepest node. Nodes at the same depth are on the same level within the tree. The root is at level 0 and has a depth of 0. A leaf node is a node with no children, while an internal node has at least one non-empty child.
A recursive data structure is a data structure that includes smaller or simpler instances of the same data structure within itself. Linked lists and binary trees are examples of recursive data structures. In a linked list, it can be defined as either an empty list or a node followed by another list. Similarly, a binary tree is commonly defined as an empty tree or a node connected to two binary trees, one serving as its left child and the other as its right child.
You have attempted of activities on this page.
