The same list, back to inorder binary tree

Question

Anoniem · 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()

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
}

Anoniem · Answer

maybe, it likes a binary tree insert problem

Anoniem · Answer

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

Meta

Sollicitatievraag bij Meta

Antwoorden op sollicitatievragen

Gevolgde bedrijven

Vacatures