Depth-first search
This approach involves backtracking for traversal and the deepest node is visited first and then backtracks up to the parent. There are three types of DFS traversal:-
- Preorder
- Inorder
- postorder
PreOrder
In pre-order traversal of a binary tree, we first traverse the root, then the left subtree, and then finally the right subtree. We do this recursively to benefit from the fact that left and right subtrees are also trees.
The steps to follow.
- Create a function traverse and call it on the root
- call traverse on the left sub-tree.
- call traverse on the right sub-tree.
InOrder
In the In-order traversal of a binary tree, we first traverse the left subtree, then traverse the root, and then finally the right subtree. We do this recursively to benefit from the fact that left and right subtrees are also trees.
The steps to follow.
- call traverse on the left sub-tree.
- Create a function traverse and call it on the root
- call traverse on the right sub-tree.
PostOrder
In post-order traversal of a binary tree, we first traverse the left subtree, then the right subtree, and then finally the root. We do this recursively to benefit from the fact that left and right subtrees are also trees.
JavaScript implementation:-
class Node{ constructor(val){ this.val = val; this.left = null; this.right = null; } } class BST{ constructor(){ this.root = null; } insert(val){ let newNode = new Node(val); if(!this.root){ this.root = newNode; }else{ let current = this.root; while(true){ if(val < current.val){ if(current.left === null){ current.left = newNode; return this }else{ current = current.left; } }else{ if(current.right === null){ current.right = newNode; return this }else{ current = current.right } } } } } find(val){ let current = this.root; let found = false; while(current && !found){ if(val < current.val){ if(current.val === val){ found = true; return current; }else{ current = current.left; } }else{ if(current.val === val){ found = true; return current; }else{ current = current.right; } } } return 'not found' } DFSPreOrder(){ let data=[]; function traverse(node){ data.push(node.val); if(node.left) traverse(node.left); if(node.right) traverse(node.right); } traverse(this.root); return data; } DFSPostOrder(){ let data=[]; function traverse(node){ if(node.left) traverse(node.left); if(node.right) traverse(node.right); data.push(node.val); } traverse(this.root); return data; } DFSInOrder(){ let data=[]; function traverse(node){ if(node.left) traverse(node.left); data.push(node.val); if(node.right) traverse(node.right); } traverse(this.root); return data; } } Python implementation:-
class Node: def __init__(self,val): self.val = val self.left = None self.right = None class BST: def __init__(self): self.root= None def insert(self, val): newNode = Node(val) if self.root == None: self.root= newNode else: current = self.root while True: if val< current.val: if current.left == None: current.left = newNode return self else: current= current.left else: if(current.right == None): current.right = newNode return self else: current = current.right def find(self, val): current= self.root found = False while current and not found: if val < current.val: current = current.left elif val > current.val: current= current.right else: found = True if(not found): return "not found" return current def dfspreorder(self): data =[] def traverse(node): data.append(node.val) if(node.left): traverse(node.left) if(node.right): traverse(node.right) traverse(self.root) return data def dfsInorder(self): data =[] def traverse(node): if(node.left): traverse(node.left) data.append(node.val) if(node.right): traverse(node.right) traverse(self.root) return data def dfspostorder(self): data =[] def traverse(node): if(node.left): traverse(node.left) if(node.right): traverse(node.right) data.append(node.val) traverse(self.root) return data bst = BST() bst.insert(100) bst.insert(200) bst.insert(150) bst.insert(175) bst.insert(160) bst.insert(180) bst.insert(75) bst.insert(50) bst.insert(65) bst.insert(40) bst.insert(55) bst.insert(20) print(bst.bfs()) print(bst.dfspreorder()) 
Top comments (0)