Trees:Binary Tree Traversals

By -

Binary Trees and Properties

Binary trees were defined in Section 3.1. For convenience, a binary tree is sometimes extended by adding external nodes. External nodes are imaginary nodes that are added wherever an empty subtree was present in the original tree. The original tree nodes are known as internal nodes. Figure 3.5(a) shows a binary tree and (b) the corresponding extended tree. Observe that in an extended binary tree, all internal nodes have degree 2 while all external nodes have degree 0. (Some authors use the term full binary tree to denote a binary tree whose nodes have 0 or two children.) The external path length of a tree is the sum of the lengths of all root-to-external node paths in the tree. In the example, this is 2 + 2 + 3 + 3 + 2 = 12. The internal path length is similarly defined by adding lengths of all root-to-internal node paths. In the example, this quantity is 0 + 1 + 1 + 2 = 4.

Properties

LEMMA 3.2 A binary tree with n internal nodes has n + 1 external nodes.

image

Proof Each internal node in the extended tree has branches leading to two children. Thus, the total number of branches is 2n. Only n − 1 internal nodes have a single incoming branch from a parent (the root does not have a parent). Thus, each of the remaining n +1 branches points to an external node.

LEMMA 3.3 For any non-empty binary tree with n0 leaf nodes and n2 nodes of degree 2, n0 = n2 + 1.

Proof Let n1 be the number of nodes of degree 1 and n = n0 + n1 + n2 (Eq. 1) be the total number of nodes. The number of branches in a binary tree is n − 1 since each non-root node has a branch leading into it. But, all branches stem from nodes of degree 1 and 2. Thus, the number of branches is n1 + 2n2. Equating the two expressions for number of branches, we get n = n1 + 2n2 + 1 (Eq. 2). From Eqs. 1 and 2, we get n0 = n2 + 1.

LEMMA 3.4 The external path length of any binary tree with n internal nodes is 2n greater than its internal path length.

Proof The proof is by induction. The lemma clearly holds for n = 0 when the internal and external path lengths are both zero. Consider an extended binary tree T with n internal nodes. Let ET and IT denote the external and internal path lengths of T . Consider the extended binary tree S that is obtained by deleting an internal node whose children are both external nodes (i.e., a leaf) and replacing it with an external node. Let the deleted internal node be at level l. Thus, the internal path length decreases by l while the external path length decreases by 2(l + 1) − l = l + 2. From the induction hypothesis, ES = IS + 2(n − 1). But, ET = ES + l + 2 and IT = IS + l. Thus, ET − IT = 2n.

LEMMA 3.5 The maximum number of nodes on level i of a binary tree is 2i, i ≥ 0.

Proof This is easily proved by induction on i.

LEMMA 3.6 The maximum number of nodes in a binary tree of height k is 2k+1 − 1.

Proof Each level i, 0 ≤ i ≤ k, has 2i nodes. Summing over all i results in ),k 2i = 2k+1 − 1.

LEMMA 3.7 The height of a binary tree with n internal nodes is at least llog2(n + 1)l and at most n − 1.

Proof The worst case is a skewed tree (Figure 3.6(a)) and the best case is a tree with 2i nodes at every level i except possibly the bottom level (Figure 3.6(b)). If the height is h, then n + 1 ≤ 2h, where n + 1 is the number of external nodes.

image

LEMMA 3.8 The number of distinct binary trees with n nodes is image 

Proof

For a detailed proof, we refer the reader to [7]. However, we note that Cn = image are known as the Catalan numbers, which occur frequently in combinatorial problems. The Catalan number Cn also describes the number of trees with n + 1 nodes and the number of binary trees with 2n + 1 nodes all of which have 0 or 2 children.

Comments

Post a Comment

Popular posts from this blog

0/1 Knapsack Problem Memory function.

By -
Image
0 / 1 Knapsack Problem Memory function Definition: Given a set of n items of known weights w1,…,wn and values v1,…,vn and a knapsack of capacity W, the problem is to find the most valuable subset of the items that fit into the knapsack. Knapsack problem is an OPTIMIZATION PROBLEM Dynamic programming approach to solve knapsack problem Step 1: Identify the smaller sub-problems. If items are labeled 1..n, then a sub-problem would be to find an optimal solution for Sk = {items labeled 1, 2, .. k } Step 2: Recursively define the value of an optimal solution in terms of solutions to smaller problems. Initial conditions: S te p 3: Bottom up computation using iteration Question: Apply bottom-up dynamic programming algorithm to the following instance of the knapsack problem Capacity W= 5 Solution: Using dynamic programming approach, we have: What is the composition of the optimal subset? The composition of the optimal subset if found by tracing back the computations for the...
Read more

Binary Space Partitioning Trees:BSP Tree as a Hierarchy of Regions.

By -
Image
BSP Tree as a Hierarchy of Regions Another way to look at BSP Trees is to focus on the hierarchy of regions created by the recursive partitioning, instead of focusing on the hyperplanes themselves. This view helps us to see more easily how intersections are efficiently computed. The key idea is to think of a BSP Tree region as serving as a bounding volume: each node v corresponds to a convex volume that completely contains all the geometry represented by the sub tree rooted at v . Therefore, if some other geometric entity, such as a point, ray, object, etc., is found to not intersect the bounding volume, then no intersection computations need be performed with any geometry within that volume. Consider as an example a situation in which we are given some test point and we want to find which object if any this point lies in. Initially, we know only that the point lies somewhere space ( Figure 20.12). By comparing the location of the point with respect to the first partitioning hyper pl...
Read more

Drawing Trees:HV-Layout

By -
Image
HV-Layout An hv -layout of a binary tree is an upward (but not strictly upward) straight line orthogonal drawing with edges drawn as rightward horizontal or downward vertical segments. The ”hv” stands for horizontal-vertical. For any vertex v in a binary tree T we either have: 1. A child of v is either • aligned horizontally with v and to the right of v or • vertically aligned below v . 2. The smallest rectangles that cover the area of the subtrees of the children of v in the layout do not intersect. Figure 45.12 shows an example of a hv -layout A hv -layout is generated by applying a dived and conquer approach. The divide step constructs the hv -layout of the left and the right subtrees, while the conquer step either performs a ho rizontal or a ver t i c a l combination . Figure 45.13 shows the two types of com- bination. If the left subtree a node v is placed to the left in a horizontal combination and below in a vertical combination, the layout preserves ...
Read more