DEV Community

Discussion on: Write better code: Day 7 - Binary Search Tree

View post
Collapse
 
arjunrajkumar profile image
Arjun Rajkumar • • Edited

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.