Traversals - 401-advanced-javascript-jonnygraybill/data-structures-and-algorithms GitHub Wiki

BST

In-Order

In-Order

• inorder(node) – It performs inorder traversal of a tree starting from a given node
• Algorithm for inorder:
  • Traverse the left subtree i.e perform inorder on left subtree
  • Visit the root
  • Traverse the right subtree i.e perform inorder on right subtree

inorder(node) 
{ 
    if(node !== null) 
    { 
        this.inorder(node.left); 
        console.log(node.data); 
        this.inorder(node.right); 
    } 
} 

Pre-Order

• preorder(node) – It performs preorder traversal of a tree starting from a given node.
• Algorithm for preoder:
  • Visit the root
  • Traverse the left subtree i.e perform inorder on left subtree
  • Traverse the right subtree i.e perform inorder on right subtree

preorder(node) 
{ 
    if(node != null) 
    { 
        console.log(node.data); 
        this.preorder(node.left); 
        this.preorder(node.right); 
    } 
}

Post-Order

• postorder(node) – It performs postorder traversal of a tree starting from a given node.
• Algorithm for postorder:
  • Traverse the left subtree i.e perform inorder on left subtree
  • Traverse the right subtree i.e perform inorder on right subtree
  • Visit the root

postorder(node) 
{ 
    if(node != null) 
    { 
        this.postorder(node.left); 
        this.postorder(node.right); 
        console.log(node.data); 
    } 
} 

Breadth-First

• Visit left-to-right, each node of each level of the BST

levelOrder() {
		if (!this.root) return null;

		const queue = [this.root],
			result = [];

		while (queue.length) {
			const front = queue.shift();
			result.push(front.value);
			if (front.left) queue.push(front.left);
			if (front.right) queue.push(front.right);
		}

		return result;

	}

Linked List

• Walk through every node in the linked list, until you get to a node that has a "next" link of "null"

``javascript while (current.next) { current = current.next; }

* To Remove:

  * If the value to be removed is the head, set the head to the next node
  * Else, we have to instantiate a "previous" variable that gets assigned to "current"
  * While current !== value we're looking for, previous = current, and current = current.next
  * To perform the removal: previous.next = current.next. This removes the node we want without breaking the remaining links between all the remaining nodes.
  * Decrement the length property.