Binary Tree

Binary TREE

A tree is a non linear data structure in which items are arranged in a sorted sequence.

Terminology

• A is the root node.

• B is the parent of D and E.

• C is the sibling of B

• D and E are the children of B.

• D, E, F, G, I are external nodes, or leaves.

• A, B, C, H are internal nodes.

• The depth (level) of E is 2

• The height of the tree is 3.

• The degree of node B is 2.

Binary Trees

• Ordered tree: the children of each node are ordered.

• Binary tree: ordered tree with all internal nodes of degree 2.

• Recursive definition of binary tree:

• A binary tree is either

– an external node (leaf), or

– an internal node (the root) and two binary trees (left subtree and right subtree)

TRAVERSING TREES

• preorder traversal

Algorithm preOrder(v)

“visit” node v

for each child w of v do

recursively perform preOrder(w)

eg. reading a document from beginning to end

• postorder traversal

Algorithm postOrder(v)

for each child w of v do

recursively perform postOrder(w)

“visit” node v

• inorder traversal

Algorithm inOrder(v)

recursively perform inOrder(leftChild(v))

“visit” node v

recursively perform inOrder(rightChild(v))