COMP 2402 Chapter Notes - Chapter 6: Binary Search Tree, Longest Path Problem, Binary Tree
Document Summary
Binary tree - a connected, undirected, finite graph with no cycles, and no vertex of degree greater than 3. In comp. sci. binary trees are rooted: a special node r, of degree at most 2 is called the root of the tree. For every other node u, the second node on the path from u to r is called the parent of u. Each other node adjacent to u is called a child of u. Depth of a node a node u is the length of the path of u to the root. A node w, on the path from u to r, is called an ancestor of u and u is a descendant of w. The subtree of node u is the binary tree rooted at u and contains all of u"s descendants. Height of a node u is the length is the longest path from u to one of its descendants.