Skip to content

Instantly share code, notes, and snippets.

@cleicar
Last active June 28, 2023 14:53
Show Gist options
  • Save cleicar/76911673b34739859e6c10eaeb80786a to your computer and use it in GitHub Desktop.
Save cleicar/76911673b34739859e6c10eaeb80786a to your computer and use it in GitHub Desktop.
Get the largest branch in a Binary Tree in Ruby
class BinaryTree
def initialize
@root = nil
@left_nodes = []
@right_nodes = []
end
def insert(value)
@root.nil? ? @root = TreeNode.new(value) : @root.insert(value)
end
def calculate_nodes(node = @root)
return if node.nil?
unless node.left&.value.nil?
@left_nodes << node.left.value
calculate_nodes(node.left)
end
unless node.right&.value.nil?
@right_nodes << node.right.value
calculate_nodes(node.right)
end
end
def largest_branch
calculate_nodes
return "" if @left_nodes.size == @right_nodes.size
@left_nodes.size > @right_nodes.size ? "Left" : "Right"
end
end
class TreeNode
attr_accessor :value, :left, :right
def initialize(value)
@value = value
@left = nil
@right = nil
end
def insert(value)
if value <= @value
@left.nil? ? @left = TreeNode.new(value) : @left.insert(value)
else
@right.nil? ? @right = TreeNode.new(value) : @right.insert(value)
end
end
end
tree = [3, 6, 2, 9, -1, 10]
bt = BinaryTree.new
tree.each { |t| bt.insert(t) }
print bt.largest_branch
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment