Converting a binary tree into a doubly linked list.

Question

Avi · Accepted Answer

Swift version, assuming you have a prefilled binary tree:

class LinkedList {
    
    var rootItem : LinkedListItem?
    var lastItem : LinkedListItem?
    
    init() {
        
    }
    
    func insertItem(value : String) {
        let newItem = LinkedListItem(value: value)
        if rootItem == nil {
            rootItem = newItem
        } else {
            newItem.previous = lastItem
            lastItem?.next = newItem
        }
        
        lastItem = newItem
    }
    
    func desc()->String {
        var str = ""
        var currentItem = rootItem
        while currentItem != nil {
            if let val = currentItem?.value {
                str += val + " -> "
            }
            currentItem = currentItem?.next
        }
        return str
    }
}

class LinkedListItem {
    var value = ""
    var next : LinkedListItem?
    weak var previous : LinkedListItem?
    
    init(value : String) {
        self.value = value
    }
}

func getLinkedList(from binaryTree : BinaryTree, linkedList : LinkedList){
    
    guard binaryTree.value.count > 0 else {
        return
    }    
    
    if let left = binaryTree.left {
        getLinkedList(from: left, linkedList: linkedList)
    }
    
    linkedList.insertItem(value: binaryTree.value)

    if let right = binaryTree.right {
        getLinkedList(from: right, linkedList:linkedList)
    }
}

let linkedList = LinkedList()
getLinkedList(from: tree, linkedList: linkedList)

Meta

Meta Interview Question

Interview Answer

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches