More

    [APPROACH] CHECK IF A BINARY TREE IS A BINARY SEARCH TREE (BST)

    PROBLEM

    Given a binary tree, find out if it is a binary search tree or not.

    APPROACH 1

    • You can traverse the tree in in-order way, and see if the elements are ascending.
      • You may either put the elements into an array and see if the array is sorted in ascending way,
      • or while traversing see if the current element is always greater than or equal to previous element.
        • return false is current data is less than previously printed data.
        • may use a static variable to hold the last printed value.

    APPROACH 2

    • For a BST, all left nodes should be less than or equal to current node and current node must be less than all right nodes.
    • We will have a recursive function that checks if this property is true for root node and all its sub trees:
      • If the method get null node, it may return true, and should be first checked (exit condition for the recursion).
      • Check if all left nodes are less than or equal to current node and current node is less than all right nodes
        • Pass current minimum and current data to left subtree
        • Pass current data and current max to right sub trees.

    Recent Articles

    OAUTH – FREQUENTLY ASKED QUESTIONS FOR INTERVIEWS AND SELF EVALUATION

    Why is refresh token needed when you have access token? Access tokens are usually short-lived and refresh tokens are...

    SUMO LOGIC VIDEOS AND TUTORIALS

    Sumo Logic Basics - Part 1 of 2 (link is external) (Sep 29, 2016)Sumo Logic Basics - Part 2 of 2...

    GIT – USEFUL COMMANDS

    Discard all local changes, but save them for possible re-use later:  git stash Discarding local changes...

    DISTRIBUTED COMPUTING – RECORDED LECTURES (BITS)

    Module 1 - INTRODUCTION Recorded Lecture - 1.1 Introduction Part I – Definition

    BOOK REVIEW GUIDELINES FOR COOKBOOKS

    Whenever you add reviews for the book, please follow below rules. Write issues in an excel.Create an excel...

    Related Stories

    Leave A Reply

    Please enter your comment!
    Please enter your name here

    Stay on op - Ge the daily news in your inbox