O'Reilly logo

Learning Functional Data Structures and Algorithms by Raju Kumar Mishra, Atul Khot

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Verifying the transformation

In-order traversal of a BST is a recursive traversal algorithm. It visits the BST tree nodes in a predefined order and always prefers to visit the left child first, then the parent itself, and finally the right child.

Verifying the transformation

As you probably know, the visiting order is also the sorted order. If we put the values in an array as shown in the diagram, we get all the values sorted:

Verifying the transformation

This traversal comes as a very useful tool to understand rotations. We can transform the tree, provided the in-order traversal visits the nodes in the ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required