How to create tree from struct

General Usage
, ,
1

I want to create tree with struct. Here’s my approach:

mutable struct node{T}
  data::T
  left::node
  right::node
  node(T)= (data=T; left= Nothing; right= Nothing)
end

root=node(1)
root.left=node(2)
root.right=node(3)
root.right.left=node(4)
root.right.right=node(5)

, but it doesn’t work. Later I want also create function to compute the “height” of a tree, that means the number of nodes along the longest path from the root node down to the farthest leaf node.
That would be something like that:

function height(root) 
    if root === Nothing 
        return 0 
    else  
        lheight = height(root.left) 
        rheight = height(root.right) 
        if lheight > rheight  
            return lheight+1
        else
            return rheight+1
        end
      end
    end
  end

and all the level and order printing functions.

1 Like
2 
mutable struct node{T}
  data::T
  left::Union{node, Nothing}
  right::Union{node, Nothing}
  node(T)= (data=T; left= Nothing; right= Nothing)
end

You need to make left/right a Union of node and Nothing so you can assign nothing to it.

5 Likes
3

First of all, inner constructor of node is not quite correct, since you try to store type instead of data itself. Secondly you do not need to use Nothing to distinguish between initialized and not initialized nodes, since you can use incomplete initialization. You may find these links useful: inner constructor and
incomplete initialization. So, your example can be rewritten as

mutable struct node{T}
  data::T
  left::node
  right::node
  node(x::T) where T = new{T}(x)
end

function height(root) 
    lheight = isdefined(root, :left) ? height(root.left) : 0
    rheight = isdefined(root, :right) ? height(root.right) : 0
    return max(lheight, rheight) + 1
end

So, as you can see

root = node(1)
# node{Int64}(1, #undef, #undef)

and for height function:

root = node(1)
root.left = node(2)
root.right = node(3)
root.right.left = node(4)
root.right.right = node(5)

height(root)
# 3
3 Likes
4

Of course you can use your original approach, but it would be more suitable to apply multiple dispatch:

mutable struct node{T}
    data::T
    left::Union{Nothing, node}
    right::Union{Nothing, node}
end

node(x::T) where T = node{T}(x, nothing, nothing)

height(root::Nothing) = 0
height(root) = max(height(root.left), height(root.right)) + 1

Note also, that while type is Nothing object of this type is nothing

4 Likes
5

Both are working, but this one looks more “pythonic”, so I choose that as a solution. Thank you