DSA

• Binary Tree


  Every node has at most two children<|>Each child node is labeled as being either a left child or a right child<|>Both subtrees (left subtree and right subtree) are themselves binary trees
• Binary Tree

  • Full binary tree: each node is either a leaf or has exactly two children
  • Complete binary tree: all levels, except possibly the last level, are completely full, and the last level has all its nodes to the left side

  
• Theorem: Let T be a binary tree. For every h ≥ 0, there are no more than 2^h leaves in level h.
• Theorem: A perfect binary tree of height h has 2^(h+1) - 1 nodes.

  
• The number of nodes n in a complete binary tree is between 2^k (minimum) and 2^(h+1) -1 (maximum)

  
• Representing binary tree with array

  A choice for a complete or almost complete binary tree<|>Root always in the array[0]<|>If parent is at array[i], then left child at array[2i+1] and right child at array[2i+2]<|>If data for a non-root appears in array[i], then its parent is at location [(i-1)/2]
• Representing binary tree with linked list

  A good choice if the binary tree is not complete or almost complete<|>Every node has two pointers: llink points to the root node of the left subtree, rlink points to the root node of the right subtree

  
• Typical binary tree operations

  • Determine if binary tree is empty
  • Search binary tree for a particular item
  • Insert an item in the binary tree
  • Delete an item from the binary tree
  • Find the height of the binary tree
  • Find the number of nodes in the binary tree
  • Find the number of leaves in the binary tree
  • Copy the binary tree
  • Traverse the binary tree

  
• Binary tree traversal algorithms

  
• btree


  Binary Tree
• Representing Binary Tree with Linked List

  
• Node of a binary tree

  Stores data in info

  Has a pointer to the left child in llink

  Has a pointer to the right child in rlink
• Root node

  A pointer to the root node is stored outside the binary tree in a pointer variable, usually called the root, of type binaryTreeNode
• Typical Binary Tree Operations

  • Determine if binary tree is empty

  Search binary tree for a particular item

  Insert an item in the binary tree

  Delete an item from the binary tree

  Find the height of the binary tree

  Find the number of nodes in the binary tree

  Find the number of leaves in the binary tree

  Copy the binary tree

  Traverse the binary tree
• Binary Tree Traversal Algorithms

  • Inorder traversal

  Preorder traversal

  Postorder traversal

  
• Binary Tree Traversal

  Start at the root node

  For each node, choose to either visit the node first or visit the subtrees first

  
• Inorder Traversal

  Left, root, right
• Inorder Traversal Sequence

  • D, G, B, E, A, C, H, F
• Preorder Traversal

  Root, left, right
• Postorder Traversal

  Left, right, root
• Postorder Traversal Sequence

  • G, D, E, B, H, F, C, A
• To summarise, the three traversal algorithms are:
• Given the preorder and inorder sequences of a binary tree, we can draw the binary tree

  
• Binary Search Tree (BST)

  A special kind of binary tree where:

  • Every node's data is larger than the data in its left child
  • Every node's data is smaller than the data in its right child
• Typical BST Operations

  • Search the BST for a particular item

  Insert an item in the BST

  Delete an item from the BST

  Find the height of the BST

  Find the number of nodes in the BST

  Find the number of leaves in the BST

  Traverse the BST

  Copy the BST
• Search an Item in BST

  Traverse the tree from root to left recursively until left is NULL

  The minimum value is the node whose left node is NULL

  Traverse the tree from root to right recursively until right is NULL

  The maximum value is the node whose right node is NULL
• Insert in BST


  See code function insert, pp. 6201-621
• Draw a Binary Search Tree

  • 45

  25

  65

  15

  30

  55

  75

  10

  20

  50

  60

  80
• Different sequences will generate different BSTs
• Delete an Element in BST

  Consider four cases:

  1. The node to be deleted is a leaf - just delete it

  2. The node to be deleted has no left child but it has a right child - replace it with its right child

  3. The node to be deleted has no right child but it has a left child - replace it with its left child

  4. The node to be deleted has both children (left and right nodes) - replace it with the minimum element from its right subtree or the maximum element from its left subtree
• Time Complexity of BST Operations