08: binary trees #1

Searching | Unbalanced Insertion | Traversal | Deletion | Threaded Trees | Tree Parameters

Binary Tree Search

Binary Tree Search has a time complexity that is proportional to the height of the tree. At each element, the left hand side element is smaller and the right hand side element is greater. If the height is h, the max search time is O(lg(h)).
  1. Start: BinaryTreeSearch
  2. Searching for 17, Start at root. BinaryTreeSearch
  3. 17 is less than 20, go to left node. BinaryTreeSearch
  4. 17 is greater than 10, go to right node. BinaryTreeSearch
  5. 17 is greater than 15, go to right node. found 17. BinaryTreeSearch

Binary Tree Insertion

To insert we search down to the lowest level and then insert when we get to NULL
  1. Start: BinaryTreeInsert
  2. Insert 10 BinaryTreeInsert
  3. Insert 40 BinaryTreeInsert
  4. Insert 5 BinaryTreeInsert
  5. Insert 15 BinaryTreeInsert
  6. Insert 45 BinaryTreeInsert
  7. Insert 2 BinaryTreeInsert
  8. Insert 11 BinaryTreeInsert
  9. Insert 17 BinaryTreeInsert
  10. Insert 43 BinaryTreeInsert
  11. Insert 45 BinaryTreeInsert

Binary Tree Traversal

Traversal is the process of visiting each node exactly once in a specified order.

Breadth-First Traversal

A queue is used for breadth-first traversal. After a node is visited it's children are put on the end of the queue. No child of a level is visited until all nodes in the current level are visited because the children are behind the current level in the queue.

Visitation order:
  • [20 10 40 5 15 45 2 11 17 43 53]
BinarySearchTree

Depth-First Traversal

Tasks of interest in this type of traversal
  • V - visiting a node
  • L - traversing the left subtree
  • R - traversing the right subtree
Three standard traversals:
  • VLR - preorder tree traversal
  • LVR - inorder tree traversal
  • LRV - postorder tree traversal
Visitation orders:
  • Preorder: [20 10 5 2 15 11 17 40 45 43 53]
  • Inorder: [2 5 10 11 15 17 20 40 43 45 53]
  • Postorder: [2 5 11 17 15 10 43 53 45 40 20]
BinarySearchTree

Binary Tree Deletion

Binary Tree Deletion has several cases:

Deleting a Leaf

  1. Start:
    BinaryTreeDelete
  2. Delete 43. Seek to node and keep track of parent.
    BinaryTreeDelete
  3. Delete curr and set parent->left = NULL
    BinaryTreeDelete

Deleting a Node with One Child

  1. Start:
    BinaryTreeDelete
  2. Delete 45. Seek to node and keep track of parent.
    BinaryTreeDelete
  3. Delete curr and set parent->right = curr->right
    BinaryTreeDelete

Deletion by Merging

When there are multiple nodes as children of a node to delete, more complicated solutions are needed. BinaryTreeDeleteByMerging

Deletion by Copying

BinaryTreeDeleteByMerging

Threaded Trees

A threaded binary tree has normally null pointers point to the predecessor or successor of nodes.
  • An inorder threaded binary tree has normally null right pointers point to the successor

Computation of Tree Parameters

1:  
// treeParameters.cpp - download here

2:  

3:  
#include
 
<
iostream>

4:  

5:  
class
 
TreeNode 
{

6:  
public
:

7:  
 
 
TreeNode(
int
 
value)
;

8:  
 
 
int
 
getValue(
)
;

9:  
 
 
void
 
setLeft(
TreeNode 
left)
;

10: 
 
 
void
 
setRight(
TreeNode 
right)
;

11: 
 
 
TreeNode 
getLeft(
)
;

12: 
 
 
TreeNode 
getRight(
)
;

13: 
private
:

14: 
 
 
int
 
m_Value;

15: 
 
 
TreeNode 
m_Left;

16: 
 
 
TreeNode 
m_Right;

17: 
}
;

18: 

19: 
TreeNode:
:
TreeNode(
int
 
value)

20: 
 
 
:
 
m_Value(
value)
m_Left(
NULL)
m_Right(
NULL)

21: 
{

22: 
}

23: 

24: 
int
 
TreeNode:
:
getValue(
)
{

25: 
 
 
return
 
m_Value;

26: 
}

27: 

28: 
void
 
TreeNode:
:
setLeft(
TreeNode 
left)
{

29: 
 
 
m_Left 
=
 
left;

30: 
}

31: 

32: 
void
 
TreeNode:
:
setRight(
TreeNode 
right)
{

33: 
 
 
m_Right 
=
 
right;

34: 
}

35: 

36: 
TreeNode 
TreeNode:
:
getLeft(
)
{

37: 
 
 
return
 
m_Left;

38: 
}

39: 

40: 
TreeNode 
TreeNode:
:
getRight(
)
{

41: 
 
 
return
 
m_Right;

42: 
}

43: 

44: 
TreeNode 
makeTree(
)
{

45: 
 
 
TreeNode 
root 
=
 
new
 
TreeNode(
20)
;

46: 
 
 
TreeNode 
left0 
=
 
new
 
TreeNode(
10)
;

47: 
 
 
TreeNode 
right0 
=
 
new
 
TreeNode(
40)
;

48: 
 
 
root->
setLeft(
left0)
;

49: 
 
 
root->
setRight(
right0)
;

50: 
 
 
TreeNode 
leftleft1 
=
 
new
 
TreeNode(
5)
;

51: 
 
 
TreeNode 
leftright1 
=
 
new
 
TreeNode(
15)
;

52: 
 
 
left0->
setLeft(
leftleft1)
;

53: 
 
 
left0->
setRight(
leftright1)
;

54: 
 
 
leftleft1->
setLeft(
new
 
TreeNode(
2)
)
;

55: 
 
 
leftright1->
setLeft(
new
 
TreeNode(
11)
)
;

56: 
 
 
leftright1->
setRight(
new
 
TreeNode(
17)
)
;

57: 
 
 
TreeNode 
rightright1 
=
 
new
 
TreeNode(
45)
;

58: 
 
 
right0->
setRight(
rightright1)
;

59: 
 
 
rightright1->
setLeft(
new
 
TreeNode(
43)
)
;

60: 
 
 
rightright1->
setRight(
new
 
TreeNode(
53)
)
;

61: 
 
 
return
 
root;

62: 
}

63: 

64: 
//Robert Sedgewick, Algorithms in C++, Parts 1-4, page 250.

65: 
int
 
countNodes(
TreeNode 
curr)
{

66: 
 
 
if
(
curr 
=
=
 
NULL)
{

67: 
 
 
 
 
return
 
0;

68: 
 
 
}

69: 
 
 
return
 
countNodes(
curr->
getLeft(
)
)
 
countNodes(
curr->
getRight(
)
)
 
1;

70: 
}

71: 

72: 
//Robert Sedgewick, Algorithms in C++, Parts 1-4, page 250.

73: 
int
 
calcHeight(
TreeNode 
curr)
{

74: 
 
 
if
(
curr 
=
=
 
NULL)
{

75: 
 
 
 
 
return
 
0;

76: 
 
 
}

77: 
 
 
int
 
left_height 
=
 
calcHeight(
curr->
getLeft(
)
)
;

78: 
 
 
int
 
right_height 
=
 
calcHeight(
curr->
getRight(
)
)
;

79: 
 
 
if
(
left_height 
>
 
right_height)
{

80: 
 
 
 
 
return
 
left_height 
1;

81: 
 
 
}
 
else
 
{

82: 
 
 
 
 
return
 
right_height 
1;

83: 
 
 
}

84: 
}

85: 

86: 
int
 
main(
int
 
argc, 
char
 
argv[
]
)
{

87: 

88: 
 
 
TreeNode 
root 
=
 
makeTree(
)
;

89: 
 
 
std:
:
cout 
<
<
 
"num nodes: "
 
<
<
 
countNodes(
root)
 
<
<
 
std:
:
endl;
 

90: 
 
 
std:
:
cout 
<
<
 
"height: "
 
<
<
 
calcHeight(
root)
 
<
<
 
std:
:
endl;

91: 
 
 
//prints:

92: 
 
 
//  num nodes: 11

93: 
 
 
//  height: 4

94: 

95: 
 
 
return
 
0;

96: 
}

97: