logo
logo

Preorder Traversal

Lesson

Implement the pre-order traversal on a binary tree.

Background: Pre-order traversal is a way of visiting every node in a binary tree. It begins at the root node and traverses the left subtree first, then the right subtree.

Write a function 
preOrderTraversal(node)
 that performs pre-order traversal on a binary tree, given the root node.

Example Tree:

       50
     /    \
    30     70
   /  \   /  \
  20  33 60  90

Output of Pre-Order Traversal:

50 30 20 33 40 70 60 90

Walkthrough

First, we need to create a 
Node
 class and a 
BinaryTree
 class, just like in the previous lecture. We will also need an 
insert()
 function to add nodes to the binary tree.
class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

class BinaryTree {
  constructor() {
    this.root = null;
  }

  insert(data) {
    const newNode = new Node(data);
    if (this.root === null) {
      this.root = newNode;
      return;
    }

    const insertNode = (node, newNode) => {
      if (newNode.data < node.data) {
        if (node.left === null) {
          node.left = newNode;
          return;
        } else {
          insertNode(node.left, newNode);
        }
      } else {
        if (node.right === null) {
          node.right = newNode;
          return;
        } else {
          insertNode(node.right, newNode);
        }
      }
    }

    insertNode(this.root, newNode);
  }
}
Next, we will create the 
preOrderTraversal(node)
 function. It will take in the root node of the binary tree and print out the nodes in pre-order traversal.
preOrderTraversal(node) {
  if (node === null) {
    return;
  }

  console.log(node.data);
  this.preOrderTraversal(node.left);
  this.preOrderTraversal(node.right);
}
We start by checking if the node is null, which means we have reached the end of the tree. If not, we print out the current node's data, then call the 
preOrderTraversal()
 function recursively on the left subtree and right subtree.

Big O Complexity Analysis:

The time complexity of pre-order traversal on a binary tree is O(n), where n is the number of nodes in the tree. This is because we are visiting every node in the tree exactly once.

The space complexity of pre-order traversal is also O(n), due to the recursive calls on the stack.

Previous LessonNext Lesson