Department

Electrical and Computer EngineeringCourse Code

ECE244H1Professor

Tarek AbdelrahmanChapter

17This

**preview**shows pages 1-2. to view the full**7 pages of the document.** ECE244 Binary Tree

What is a binary tree?

- Structure that is either empty or consists of one node connected to two disjoint

structure

- There are unique parents for each node in the tree except for root

- Length of path = numbers of node - 1

- Path between the root and each node in the tree is unique

What is Tree Traversals?

- Visiting each node once and only once

- There are 6 possibilities but only 3 are USEFUL

➢ In-order traversal (LNR)

○ Traverse left → visit node → traverse right

➢ Pre-order traversal (NLR)

○ Visit node → traverse left → traverse right

➢ Post-order traversal (LRN)

○ Traverse left → traverse right → visit node

- Traverse left / traverse right means traverse left subtree or traverse right subtree in

the same order

Only pages 1-2 are available for preview. Some parts have been intentionally blurred.

Pre-order traversal (NLR)

- Visit node → traverse left → traverse right

(visit the left subtree first and come back to the right subtree)

What’s a Binary Search Tree?

- Binary tree is sorted when using in-order traversal (LNR)

(left subtree -> node -> right subtree)

- Each node has a key

- key of any node is greater than the keys of the nodes in its left subtree

- key of any node is less than the keys of the nodes in its right subtree

- Order: L < N < R → this is why binary tree is sorted using in-order traversal

(left subtree < node < right subtree)

< C++ Code >

treenode* searchBST(treenode* N, int skey){

if(N == NULL)

return NULL;

if(N->key == skey)

return N;

else if(N->key < skey) //must be in left subtree

return searchBST(N->R, skey);

else //must be in right subtree

return searchBST(N->L, skey);

###### You're Reading a Preview

Unlock to view full version