CS 225 Lecture Notes - Lecture 21: Binary Tree, Longest Path Problem, Null Pointer
10 Oct 2016
School
Department
Course
Professor
Document Summary
Binary tree is a discrete structure right now. A binary tree t is either empty. or null. Or root together with a left or right subtrees, each of which are binary trees, {root, T_l, t_r} tree left, tree right root without left or right {r,{},{}} An (important) example of a function on a binary tree: height(t) -- length of longest path from root to a leaf. Most common definition of height is the length of the longest path from root to a leaf. Given a tree t, write a recursive defn of the height of t, height(t): An empty tree with no root, the tree has height -1, this is base case. If the tree is not empty, then t={r,t_l. t_r} and height(t) = 1. Full binary tree: a tree in which every node has 2 or 0 children. F is a full binary tree if and only if:
