The same list, back to inorder binary tree

Question

Sigiloso · Accepted Answer

Did he tell you thats how to do it?

Carlos Carvalho · Answer

// Question 1: Binary tree to list, inorder  
class Node {
  var data: T?
  var next: Node?
  
  init(_ data: T, _ next: Node? = nil) {
    self.data = data
    self.next = next
  }
  
  func description() {
    var node: Node? = self
    var text = ""
    while(node != nil) { 
      if text.characters.count > 0 { text += "->" }
      text += "\(node!.data!)"
      node = node!.next
    }
    print(text)
  }
}

class BNode {
  var data: T?
  var left: BNode?
  var right: BNode?
  
  init(_ data: T?, l left: BNode? = nil, r right: BNode? = nil) {
    self.data = data
    self.left = left
    self.right = right
  }
}

let btree = BNode(10, l: BNode(9, 
                              l: BNode(8), r: BNode(11)), 
                           r: BNode(12, 
                              l: BNode(7), r: BNode(13))
                      )

// inorder = LVR
func binaryTreeToList(_ bnode: BNode?, _ node: inout Node?, _ head: inout Node?) {  
  if bnode == nil { return }
    
  binaryTreeToList(bnode!.left, &node, &head)    
    
  let tmp: Node? = Node(bnode!.data!)
  if node == nil {
    head = tmp
    node = tmp    
  } else {
    node!.next = tmp
  }  
  node = tmp
  
  binaryTreeToList(bnode!.right, &node, &head)    
}

func binaryTreeToList(_ bnode: BNode?) -> Node? {  
  var node: Node? = nil
  var head: Node? = nil
  binaryTreeToList(bnode, &node, &head)  
  return head
}

let list = binaryTreeToList(btree)
list!.description()

// Question 2: The same list, back to inorder binary tree  

// HINT: Identify the middle point of the list and then split recursivily

enum Position {
  case V, L, R
}

func listToBinaryTree(_ start: Node?, _ end: Node? = nil, _ root: inout BNode?, _ position: Position) {
  
  if start?.data == end?.data { return }
  
  var middle: Node? = start
  var runner: Node?  = start
  while runner?.data != end?.data {
        
    runner = runner?.next
    if runner?.data == end?.data { break }
    runner = runner?.next
    if runner?.data == end?.data { break }
    
    middle = middle?.next    
  } 
  
  if root == nil {
    root = BNode(middle!.data!)
  }
  
  let previousRoot = root // keep a reference to pop back to the previous root
  switch position {
    case .V:      
    break
    case .L:
      root!.left = BNode(middle!.data!)
      root = root!.left
    break
    case .R:
      root!.right = BNode(middle!.data!)
      root = root!.right
    break    
  }
  
  listToBinaryTree(start, middle, &root, .L)       
  listToBinaryTree(middle?.next, end, &root, .R)
  root = previousRoot
}

func listToBinaryTree(_ list: Node?) -> BNode? {
  var root: BNode? = nil
  listToBinaryTree(list, nil, &root, .V)  
  return root
}
  
let btree2 = listToBinaryTree(list)
binaryTreeToList(btree2)!.description()

Sigiloso · Answer

maybe, it likes a binary tree insert problem

Guilherme Moura · Answer

Carlos's code looks correct, I just improved it a bit by removing the need for inout and enum.


func listToBinaryTree(head: LinkedListNode) -> BNode? {
    return listToBinaryTree(start: head, end: nil)
}

func listToBinaryTree(start: LinkedListNode?, end: LinkedListNode?) -> BNode? {
    if start?.value == end?.value { return nil }
    
    var middle: LinkedListNode? = start
    var runner: LinkedListNode? = start
    while runner?.value != end?.value {
        runner = runner?.next
        if runner?.value == end?.value { break }
        runner = runner?.next
        if runner?.value == end?.value { break }
        middle = middle?.next
    }
    
    let root = BNode(value: middle!.value)
    root.left = listToBinaryTree(start: start, end: middle)
    root.right = listToBinaryTree(start: middle?.next, end: end)
    
    return root
}

Sigiloso · Answer

Couldn't answer this. Turned out it needed some recursion splitting at the middle of the list.

Meta

Pergunta de entrevista da empresa Meta

Respostas da entrevista

Empresas seguidas

Buscas de vagas