Home - gitpayal/DataStructures GitHub Wiki

Welcome to the Binary Search Tree

Binary search tree : The basic idea behind binary search tree is

• fast search and flexible update

• A rooted binary tree is recursively defined as 1. either empty 2. consisting of a node called root, together with two rooted binary tree

  • left subtree
  • right subtree

• Order matters

• A binary tree labels each node in a binary tree with single key such that for any node labeled x All nodes in the left subtree is less than x and all nodes in right subtree is greater than x.

Implementation of binary tree

• A binary tree node can be defined as follows function TreeNode(val) { this.val = val; this.left = this.right = null; }

• Basic operations supported by binary search tree are

  • searching
  • traversal
  • insertion
  • deletion

• Searching :

The important aspect of binary tree is it uniquely identifies where each key is located. We always start from root and compare with search term. if it is greater , go to right and if it is smaller, go to left the pseudo code :

searchBinaryTree(exampleTree,searchItem){ if(exampleTree == null) return null; if(exampleTree.val == searchItem) return exampleTree; if(exampleTree.val<searchTerm){ searchBinaryTree(exampleTree.left, searchItem) } else { searchBinaryTree(exampleTree.right, searchItem) } }

Searching takes O(h) where h is height of tree.

• Traversal

Visiting all nodes of binary tree proves to be very important component of many algorithms. Binary tree makes it very easy to report the labels in sorted order. By definition, all keys smaller than the root must lie in left subtree and all nodes greater than root in on right subtree

the pseudo code :

traverseBinaryTree(exampleTree){ if(exampleTree!== null){ traverseTree(exampleTree.left) processTreeVal(exampleTree.val) traverseTree(exampleTree.right) } }

Above code is basically in-order Traversal of search tree.Each node is processed once during the traversal which runs i O(n) where n is number of nodes

just swapping processTreeVal relative to left subtree and right subtree traversal will yield preOrder and postOrder traversal. if processTreeVal is done first --- preorder if processTreeVal is done first -- postOrder

PostOrdder and preorder makes a lot of sense in arithmetic or logical expression

• Insertion There is only one place to insert into a binaryTree .It combines search and allocating a node . Insertion takes O(h) time for searching and constant time for node allocation and linking is constant time.

• Finding minimum and maximum in the tree

  Minimum must be the descendent of leftmost node of the binary tree Similarly maximum is the right most node descendent.

Traversal: There are three ways od traversal to the binary search tree inorder preorder postorder

inorder :-> traverse left traverse item at node traverse right

preorder -> process item traverse left traverse right

postorder -> traverse left traverse right process item

preorder and post order are good for arithmetic and logical expressions

Deletion : there are three cases

case 1: -> when node to be deleted have no child .it has simple approach of unlinking node from tree case 2 :-> when node to be deleted have single child . connect it directly to grandparent. case 3 :-> when node t be deleted have two child.

The worst case complexity of deletion : each needs two search time of O(h) and constant time of pointer manipulation