Skip to content

Instantly share code, notes, and snippets.

@T-Pham
Last active July 25, 2016 03:13
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 T-Pham/4b72d17851162a32b2fc534f0618135d to your computer and use it in GitHub Desktop.
Save T-Pham/4b72d17851162a32b2fc534f0618135d to your computer and use it in GitHub Desktop.
Mirror tree without recursion
class Node {
var id = 0
weak var parent: Node? = nil
var left: Node? = nil {
didSet {
left?.parent = self
}
}
var right: Node? = nil {
didSet {
right?.parent = self
}
}
}
func mirror(tree: Node) -> Node {
let newTree = Node()
var original: Node! = tree
var mirrored: Node! = newTree
while original != nil {
mirrored.id = original.id
if (original.left != nil) && (mirrored.right == nil) {
original = original.left
mirrored.right = Node()
mirrored = mirrored.right
continue
}
if (original.right != nil) && (mirrored.left == nil) {
original = original.right
mirrored.left = Node()
mirrored = mirrored.left
continue
}
original = original.parent
mirrored = mirrored.parent
}
return newTree
}
var tree = Node()
tree.id = 0
tree.left = Node()
tree.left!.id = 1
tree.right = Node()
tree.right!.id = 2
tree.left!.left = Node()
tree.left!.left!.id = 3
tree.left!.right = Node()
tree.left!.right!.id = 4
//tree.right!.left = Node()
//tree.right!.left!.id = 5
tree.right!.right = Node()
tree.right!.right!.id = 6
tree.left!.left!.left = Node()
tree.left!.left!.left!.id = 7
tree.left!.left!.right = Node()
tree.left!.left!.right!.id = 8
tree.left!.right!.left = Node()
tree.left!.right!.left!.id = 9
tree.left!.right!.right = Node()
tree.left!.right!.right!.id = 10
//tree.right!.left!.left = Node()
//tree.right!.left!.left!.id = 11
//tree.right!.left!.right = Node()
//tree.right!.left!.right!.id = 12
tree.right!.right!.left = Node()
tree.right!.right!.left!.id = 13
tree.right!.right!.right = Node()
tree.right!.right!.right!.id = 14
extension Node: CustomStringConvertible {
var indent: String {
return "\t" + (parent?.indent ?? "")
}
var description: String {
return "\(id)\n"
+ ( left != nil ? "\(indent)L:\(left!)" : "" )
+ ( right != nil ? "\(indent)R:\(right!)" : "" )
}
}
print(tree)
print(mirror(tree))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment