Inorder preorder postorder обход дерева

Recursive Binary Tree Traversals: Preorder, Inorder and Postorder

Most of the time, we traverse each tree node to process data stored in tree data structure. The process of visiting all nodes of a tree is called tree traversal. It is like accessing each node only once and performing various operations (query or modification) with the data. We access data elements in sequential order in case of linear data structures (linked lists, stacks, queues, etc.). But there can be many ways to access data elements in a binary tree. Starting from the root node, there are two directions: Either we can go left via the left pointer or right via the right pointer. So what are possible options? Let’s explore!

Types of binary tree traversal using recursion

• Root node: The topmost node of a binary tree.
• Left-subtree: A smaller binary tree connected via the left pointer of root node.
• Right-subtree: A smaller binary tree connected via the right pointer of root node.

So traversing a binary tree requires traversal of each component: Processing root node, traversing the left subtree, and traversing the right subtree.

From another perspective, the left and right subtree are binary trees with fewer nodes and part of the same binary tree. So we can implement tree traversal easily using recursion i.e. dividing a problem of binary tree traversal into traversal of root and traversal of two smaller subproblems:

• Subproblem 1: Traversal of the left subtree
• Subproblem 2: Traversal of the right subtree

There can be various choices to traverse each component, where each choice accesses nodes in a different order and provide different traversal. So the classification of traversal is based on the order in which root is visited: 1) First visit root node, then traverse left or right subtree 2) First traverse either left or right subtree, then visit root node 3) First traverse left and right subtree, then visit root in the last. In other words, we have 3! or 6 possibilities, where each possibility will process nodes in a different order.

• Preorder traversal: Visit root → Traverse left subtree → Traverse right subtree
• Reverse preorder traversal: Visit root → Traverse right subtree → Traverse left subtree
• Inorder traversal: Traverse left subtree → Visit root → Traverse right subtree
• Reverse inorder traversal: Traverse right subtree → Visit root → Traverse left subtree
• Postorder traversal: Traverse left subtree → Traverse right subtree → Visit root
• Reverse postorder traversal: Traverse right subtree → Traverse left subtree → Visit root

If we simplify the classification based on order in which we visit the root node, it would get reduced to three traversals: Preorder (root first), Inorder (root second), and Postorder (root last). These traversals are also called DFS traversal of a binary tree. Note: All three reverse traversals are the mirror image of these traversals. Sometimes reverse traversals also help us to solve several binary tree coding problems.

There is another traversal method where we visit nodes in level-wise order. This is called level order traversal or breadth-first search traversal (BFS traversal). In this blog, we will discuss the idea of recursive DFS traversals. We have separately discussed the Iterative DFS traversal using stack.

Recursive preorder traversal of binary tree

In recursive preorder traversal, we first process the root node, then process all nodes in the left subtree, and finally, we process all nodes in the right subtree. Suppose we use a function preorder(root) with root as an input parameter.

Steps of recursive preorder implementation

• First, process data stored in the root node i.e. process(root->value). We can perform various data manipulation operations like printing node data, arithmetic operations, logical operations, etc.
• Then we recursively traverse and process each node in the left subtree by calling the same function with root->left as input parameter i.e. preorder(root->left).
• Then we recursively traverse and process each node in the right subtree by calling the same function with root->right as input parameter i.e. preorder(root->right).
• Base case: recursion will terminate and backtrack when it reaches the bottommost end of binary tree, i.e. root == NULL.

Pseudocode of recursive preorder traversal

class TreeNode  int data TreeNode left TreeNode right > void preorder(TreeNode root)  if (root == NULL) return process(root->data) preorder(root->left) preorder(root->right) >

Visualization of recursive preorder traversal

Application of preorder traversal

We use preorder traversal in a situation when we need to explore all tree nodes before inspecting any nodes in the left or right sub-tree.

• To create a replica or copy of a tree.
• To get the prefix expression of an expression tree.

Recursive inorder traversal of binary tree

In recursive in-order traversal, we first process all nodes in the left subtree, then root node, and finally, we process all the nodes in the right subtree. Suppose we use a function inorder(root) with root as an input parameter.

Steps of recursive inorder implementation

• We recursively traverse and process each node in the left subtree by calling the same function with root->left as input parameter i.e. inorder(root->left).
• After processing each node in the left subtree, we now process data stored in the root node i.e. process(root->data).
• Finally, we recursively traverse and process each node in the right subtree by calling the same function with root->right as input parameter i.e. inorder(root->right).
• Base case: Recursion will terminate and backtrack when it reaches the end of tree i.e. root == NULL.

Pseudocode of recursive Inorder traversal

class TreeNode  int data TreeNode left TreeNode right > void inorder(TreeNode root)  if (root == NULL) return inorder(root->left) process(root->data) inorder(root->right) >

Visualisation of Inorder traversal

Application of inorder traversal

It is commonly used in the processing of binary search trees. In BST, there is an order associated with each node: All values in the left subtree ≤ Node value ≤ All values in the right subtree. So inorder traversal of BST generates the tree data in sorted or increasing order.

Recursive postorder traversal of a binary tree

Suppose we use the function postorder(root) with root as an input parameter. Here we first process all nodes in the left subtree, then process all nodes in the right subtree, and at the end, we process the root node.

Steps of recursive postorder implementation

• We recursively traverse and process each node in the left subtree by calling the same function with root->left as input parameter i.e. postorder(root->left).
• Then we recursively traverse and process each node in the right subtree by calling the same function with root->right as input parameter i.e. inorder(root->right).
• Finally, we process data stored in the root node i.e. process(root->value).
• Base case: Recursion will terminate and backtrack when it reaches the bottommost end of tree i.e. root == NULL.

Pseudocode of recursive postorder

class TreeNode  int data TreeNode left TreeNode right > void postorder(TreeNode root)  if(root == null) return postorder(root->left) postorder(root->right) process(root) >

Visualisation of the postorder traversal

Application of postorder traversal

We use postorder traversal when we need to explore all nodes in left or right sub-tree before inspecting the root node.

Time complexity analysis of recursive DFS Traversals

In DFS traversal, we access each node once and perform constant operations with each node. Time complexity = Number of nodes * Operation count with each node = n*O(1) = O(n). Let’s visualize this by following the analysis process of recursive algorithms.

We have two different subproblems in DFS traversal: left subtree and right subtree. The size of these subproblems depends on the number of nodes present in both subtrees. Suppose:

• T(n) is the time complexity of the traversal of n size binary tree
• k nodes are present in the left subtree and n — k — 1 node on the right subtree. Here 0≤ k ≤ n — 1.
• We are doing O(1) operation with each node.

T(n) = Time complexity of traversing left subtree + Time complexity of traversing right subtree + Time complexity of processing root node = T(k) + T(n — k — 1) + O(1) = T(k) + T(n — k — 1) + c

Recurrence relation of DFS traversal: T(n) = T(k) + T(n — k — 1) + c

Case 1: Skewed binary tree

In this situation, one subtree is empty, and another subtree is non-empty. This will be the case of k = 0 or k = n — 1. Recurrence relation: T(n) = T(0) + T(n — 1) + c.

Let’s assume T(0) will be some constant, because traversing an empty tree will take some constant time => T(0) + c = d (some constant). Final recurrence relation: T(n) = T(n — 1) + d.

We can easily solve this recurrence by expanding each intermediate value of T(n — i), for 1

T(n) = T(n - 1) + d T(n) = T(n - 2) + d + d T(n) = T(n - 3) + d + d + d and so on . T(n) = T(1) + (n - 1)d T(n) = T(0) + nd = O(n)

Case 2: Balanced binary tree

In this situation, both left and right subtrees have equal number of nodes. This will the case of k = (n — 1)/2.

T(k) = T((n - 1)/2) T(n - k - 1) = T((n - 1)/2) Recurrence relation: T(n) = 2T((n - 1)/2) + c

T(n) = 2T(n/2) + c. We can easily solve this recurrence using the master theorem or recursion tree method. T(n) = O(n) (Think!). Refer to this blog: Analysis of recursive algorithms.

In both scenarios, the time complexity of DFS traversal is O(n).

The space complexity of recursive DFS traversals

Preorder, inorder and postorder traversals are different forms of depth-first search traversal, and recursive implementation looks similar. So the space complexity analysis for all DFS traversal will follow the same approach.

The space complexity of DFS traversal depends on the size of recursion call stack, which is equal to the maximum depth of recursion or the height of tree (h). In other words, at most h number of recursive calls will be stored on the call stack at any given moment i.e. compiler allocates recursion call stack of size O(h).

Best case: This is a balanced tree scenario, and the tree height will be O(logn). So the best-case space complexity of DFS traversal is O(logn).

Worst case: This is a scenario when tree is highly unbalanced, and there is only one node at each level. This tree looks similar to a singly linked list. So the height of the tree is O(n), and the worst-case space complexity of DFS traversal is O(n).

Critical ideas to think!

• Depth-first traversal starts from the root, goes to the depth as far as possible, and then backtracks from there. In other words, it visits nodes from the bottom of the tree. If we need to search for something in the depth of tree or node closer to a leaf, we prefer DFS.
• Sometimes we can solve tree coding problems using all the traversals, but in some cases, some specific traversal would be the only option that provides an efficient solution. Our goal should be to learn use cases of each depth-first search traversal in problem-solving.
• For solving binary tree problems, we perform various operations with each node during the traversal. Sometimes, we pass extra variables or pointers to the function parameters, use helper functions, use parent pointers, store some extra data inside the node, and use data structures like the stack, queue, priority queue, etc.
• What would be the average case space complexity of the DFS traversal? Let’s think!
• Understanding the order of nodes in each traversal is very important. For example, if we want to construct the binary tree from the given traversal, then one traversal is insufficient. We need at least two of the traversals i.e, preorder and postorder or preorder and inorder or postorder and inorder. Why? Think and explore.

Critical concepts to explore further!

• Iterative binary tree traversal using stack
• BFS traversal of binary tree
• Properties and types of binary tree
• Various binary tree operations like insertion, deletion, construction, height, merging, searching, and other transformation and query operations.
• Array-based implementation of the binary tree
• Properties and operations of binary search tree

Problems to solve using DFS traversals

• Left view of binary tree
• Maximum width of a binary tree
• Min depth of a binary tree
• Level with the maximum number of nodes
• Convert a binary tree into a mirror tree
• Find the diameter of a binary tree
• Find nodes at k distance from a given node
• Boundary traversal of binary tree
• The least common ancestor of two-node in a binary tree
• Construct binary tree from preorder and In-order traversal

Enjoy learning, Enjoy coding, Enjoy algorithms!

Источник