Construct BST from pre-order traversal (using monotonic stack; no recursion)

This article discusses on a way in which, Binary Search Tree (BST) can be reconstructed when corresponding pre-order traversal of the tree is input, using a concept of monotonic stack.

Table of ContentsPre-requisitesIntroductionEdition 1Edition 2Step-by-step algorithmC codeQuestionComplexityReferences Pre-requisites

Binary search tree, Stack, Binary tree traversal

Introduction

Binary search tree contains nodes with each having maximum of 2 child nodes. Nodes are arranged such ...