Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

inorder
preorder
depth first
breadth first
trees

What is tree traversal?

Educative Team

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

A tree is a widely used data structure in the world of programming. This structure, like its name, has branches and subdivisions, where each element in the tree is called a node.

For a tree to be “traversed” means that every node within the tree has been visited.

Where most data structures can be traversed in one or two ways by virtue of being linear, trees have a hierarchical structure and hence they can be traversed in multiple ways. Before we understand what these types are, we need to be familiar with a few terms.

  • root: The first node of the tree (generally portrayed as the top-most node).
  • parent: Each node that has a branch leading out from it, is called the parent of the subsequent node(s).
  • children: The node(s) that extend from the parent are called children; the left and the right child depending on the placement of the node.

Types of traversals


Depth First Traversals

  • Inorder: First, you traverse the left child and its sub-tree, visit the root and then the right child and its sub-tree.
  • Preorder: Visit the root first, then traverse the left sub-tree, and then the right sub-tree.
  • Postorder: Traverse the left sub-tree, then traverse the right sub-tree and then visit the root node.

Breadth First Traversals

  • Levelorder: This traverses nodes by levels instead of sub-trees. First, visit the root node; then visit all children of the root node- left to right. Subsequently, go down levels till you reach the node that has no children- the leaf nodes.

RELATED TAGS

inorder
preorder
depth first
breadth first
trees
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring