Skip to content

Instantly share code, notes, and snippets.

@bparanj
Created August 13, 2020 23:02
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save bparanj/d319595ae3fed70dd8451759dd88c244 to your computer and use it in GitHub Desktop.
Save bparanj/d319595ae3fed70dd8451759dd88c244 to your computer and use it in GitHub Desktop.
# Definition for a binary tree node.
# class TreeNode
# attr_accessor :val, :left, :right
# def initialize(val = 0, left = nil, right = nil)
# @val = val
# @left = left
# @right = right
# end
# end
# @param {TreeNode} root
# @return {Void} Do not return anything, modify root in-place instead.
def flatten(node)
if node.nil? || (node.left.nil? && node.right.nil?)
return
end
unless node.left.nil?
flatten(node.left)
right = node.right
node.right = node.left
node.left = nil
current = node.right
while current.right
current = current.right
end
current.right = right
end
unless node.right.nil?
flatten(node.right)
end
return node
end
@bparanj
Copy link
Author

bparanj commented Aug 18, 2020

Post order traversal:

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {TreeNode} root
# @return {Void} Do not return anything, modify root in-place instead.
def flatten(node)
    if node.nil?
        return
    end
        
    flatten(node.left)
    flatten(node.right)
    
    if node.left
        temp = node.right
        node.right = node.left
        
        current = node.right
        while current.right
            current = current.right
        end
        current.right = temp
        node.left = nil
    end
    
end

@bparanj
Copy link
Author

bparanj commented Aug 22, 2020

def flatten(node)
  if node.nil? 
      return
  end
      
  if node.left
     flatten(node.left)
     right = node.right
     node.right = node.left
     node.left = nil
     current = node.right
     while current.right
        current = current.right 
     end
     current.right = right
  end

  if node.right
     flatten(node.right) 
  end
    
  return node
end

Refactored version of first solution.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment