Write better code: Day 7 - Binary Search Tree

Updated on Jan 31, 2019 ・1 min read

Day 7: Question 1

Write a method to check that a binary tree is a valid binary search tree.

A binary search tree is a binary tree in which, for each node, the node's value is greater than all values in the left subtree, and the node's value is less than all values in the right subtree.

-

If you want to follow along, feel free to post your answers in the comment.

My answers are in the comments.
This problem is from InterviewCake.

DISCUSSION (1)
 

Input: binary tree
Output - Boolean - check if it is a binary search tree ..

Logic:

  • Do a depth first search for the tree
  • If the child node is on the left, its value has to be lesser than all parents.
  • If the child node is on the right, its value has to be greater than all parents.
  • So as you go down each node, store the lowest_value and the highest_value.
  • Then check if the current is less than the lowest_number (for left side) - and do accordingly for right side.
  • Return false if condition not met.
def binary_search_tree(one_tree)

  nodes = []
  nodes.push([one_tree, -Float::INFINITY, Float::INFINITY])

  while nodes.any?  
    node, lowest_number, highest_number = nodes.pop

    return false if ((node.current_value <= lowest_number) || (node.current_value >= highest_number))

    nodes.push([node.left, lowest_number, node.current_value]) if node.left
    nodes.push([node.left, node.current_value, highest_number]) if node.right
  end 
  true
end

This is in O[n] time.

Classic DEV Post from Aug 14 '18

What are common myths about software careers?

Whether they were once true and now outdated, or were never a thing: What are c...

Arjun Rajkumar
I’m a software developer primarily building web apps using Ruby on Rails. Working on a personal project + freelancing. I'm looking for additional freelance work so hit me up if you need help!
DEV.join()

Come for the ideas.
Stay for the community.