Swift Equatable Generic type comparison inside generic function

Question

I have a Node class for a binary tree like so:

class Node<T: Equatable> {
    let value: T
    let left: Node<T>?
    let right: Node<T>?

    init(value: T, left: Node<T>? = nil, right: Node<T>? = nil) {
        self.value = value
        self.left = left
        self.right = right
    }
}

The values need to be equatable.

I can test out the equitability like this:

let a = Node(value: 8)
let b = Node(value: 7)

let c = a.value > b.value

Which works fine, c: true

But when I write a generic function that uses the equitability of the nodes I get errors:

func isBinaryTree<T>(node: Node<T>) -> Bool {
    if let leftNode = node.left {
        guard leftNode.value < node.value else {
            return false
        }
        guard isBinaryTree(node: leftNode) else {
            return false
        }
    }
    if let rightNode = node.right {
        guard rightNode.value >= node.value else {
            return false
        }
        guard isBinaryTree(node: rightNode) else {
            return false
        }
    }

    return true
}

let result = isBinaryTree(node: root)

Errors:

error: binary operator '<' cannot be applied to two 'T' operands guard leftNode.value < node.value ||`

I'm not sure why the compiler doesn't seem to know why the T values are Equatable or why it doesn't think that the T on the leftNode is the same type as the T on the node.

The code:

let d = Node(value: Float(3), left: Node(value: Int(8)) , right: nil)

Gives an error as expected.

Looking further into this, it isn't related to the function because when I try the code:

let x = Node(value: 3, left: Node(value: 8) , right: nil)
let y = x.value < x.left!.value

I get the same error

Answer 1

In the general case, two Node objects aren't comparable. It depends on the kind of tree they're found in. It would make sense, for example, if nodes were only constrained to be valid members of a binary tree, but this isn't the case.

Luckily, you don't need Node to be Comparable, you can just need for its value to be Comparable:

class Node<T: Comparable> {
    let value: T
    let left: Node<T>?
    let right: Node<T>?

    init(value: T, left: Node<T>? = nil, right: Node<T>? = nil) {
        self.value = value
        self.left = left
        self.right = right
    }
}

extension Node: Equatable {
    static func == (lhs: Node, rhs: Node) -> Bool {
        return lhs.value == rhs.value
            && lhs.left == rhs.left
            && lhs.right == rhs.right
    }
}

extension Node {
    func isBinarySubTree() -> Bool {
        return left.map { $0.value < self.value } ?? true
            && right.map { self.value < $0.value } ?? true
            && left?.isBinaryTree() ?? true
            && right?.isBinaryTree() ?? true
    }
}