Binary Tree in Objective-C

Question

I am learning algorithms and data structures and to train I am trying to design and implement a binary tree using objective-c.

So far I have the following Classes:

• main - for testing
• Node - node of tree
• BinaryTree - for all methods related to the tree

One of the first methods in BinaryTree class I implemented is insertNode:forRoot:.

- (void)insertNodeByRef:(Node **)node forRoot:(Node **)root{

    if (head == NULL) {
        head = *node;
    }
    // Case 2 root is null so can assign the value of the node to it
    if (root == NULL) {
        root = node;
    } else {
        if (node.data > root.data) { // to the right
            [self insertNode:node forRoot:root.right];
        } else if (node.data < root.data) { //or to the left
            [self insertNode:node forRoot:root.left];
        }
    }
}

Where the interface of Node class looks like:

@interface Node : NSObject

@property(nonatomic, assign) int data;
@property(nonatomic, strong) Node * right;
@property(nonatomic, strong) Node * left;

@end

My problem is that I don't know how to access the Node class member variables if I am passing Node as a reference. Whenever I try to access the node properties (like data, left or right) I am getting the following error message:

Member reference base type 'Node *__autoreleasing *' is not a structure or union

So my questions is: how can I access those properties (data, left or right) and use them to store either int data or reference to another Node?

Hope it makes sense. Thanks!

Answer 1

Your code is mixing two common approaches to the task, hence the problem. You are also using an abstract data type (ADT) type approach, rather than an object-oriented one, so there are three approaches to consider.

In both ADT approaches your tree is represented by a reference to its root, in Objective-C this is probably stored in an instance variable:

Node *TreeRoot;

Note also that both of these algorithms use field references, a->b, rather than property references, a.b - this is because the former references a variable and the second algorithm requires passing a reference to a variable.

Functional ADT: Pass-by-value and assign result

In this approach a node is inserted into a tree and a modified tree is returned which is assigned back, e.g. the top-level call to insert a Node nodeToInsert would be:

TreeRoot = insertNode(nodeToInsert, TreeRoot);

and the insertNode function looks like:

Node *insertNode(Node *node, Node *root)
{
   if(root == nil)
   {  // empty tree - return the insert node
      return node;
   }
   else
   {  // non-empty tree, insert into left or right subtree
      if(node->data > root->data) // to the right
      {
        root->right = insertNode(node, root->right);
      }
      else if(node->data < root->data)//or to the left
      {
        root->left = insertNode(node, root->left);
      }
      // tree modified if needed, return the root
      return root;
   }
}

Note that in this approach in the case of a non-empty (sub)tree the algorithm performs a redundant assignment into a variable - the assigned value is what is already in the variable... Because of this some people prefer:

Procedural ADT: Pass-by-reference

In this approach the variable holding the root of the (sub)tree is passed-by-reference, rather than its value being passed, and is modified by the called procedure as needed. E.g. the top-level call would be:

insertNode(nodeToInsert, &TreeRoot); // & -> pass the variable, not its value

and the insertNode procedure looks like:

void insertNode(Node *node, Node **root)
{
   if(*root == nil)
   {  // empty tree - insert node
      *root = node;
   }
   else
   {  // non-empty tree, insert into left or right subtree
      Node *rootNode = *root;
      if(node->data > rootNode->data) // to the right
      {
        insertNode(node, &rootNode->right);
      }
      else if(node->data < rootNode->data)//or to the left
      {
        insertNode(node, &root->left);
      }
   }
}

You can now see that your method is a mixture of the above two approaches. Both are valid, but as you are using Objective-C it might be better to take the third approach:

Object-Oriented ADT

This is a variation of the procedural ADT - rather than pass a variable to a procedure the variable, now called an object, owns a method which updates itself. Doing it this way means you must test for an empty (sub)tree before you make a call to insert a node, while the previous two approaches test in the call. So now we have the method in Node:

- (void) insert:(Node *)node
{
   if(node.data > self.data) // using properties, could also use fields ->
   {
      if(self.right != nil)
         [self.right insert:node];
      else
         self.right = node;
   }
   else if(node.data < rootNode.data)
   {
      if(self.left != nil)
         [self.left insert:node];
      else
         self.left = node;
   }
}

You also need to change the top level call to do the same test for an empty tree:

if(TreeRoot != nil)
   [TreeRoot insert:nodeToInsert];
else
   TreeRoot = nodeToInsert;

And a final note - if you are using MRC, rather than ARC or GC, for memory management you'll need to insert the appropriate retain/release calls.

Hope that helps you sort things out.

Answer 2

First of all, don't write your methods to take Node **. It's just confusing.

Second, think about how it should work. Describe to yourself how it should work at a pretty abstract level. Translate that description directly into code, inventing new (not-yet-written!) messages where necessary. If there are steps you don't know how to do yet, just punt those off to new messages you'll write later. I'll walk you through it.

Presumably you want the public API of BinaryTree to include this message:

@interface BinaryTree

- (void)insertValue:(int)value;

So how do you implement insertValue:? Pretend you're the BinaryTree object. What's your high-level description of what you need to do to insert a value? You want to create a new Node. Then you want to insert that new Node into yourself. Translate that description directly into code:

@implementation BinaryTree {
    Node *root_; // root node, or nil for an empty tree
}

- (void)insertValue:(int)value {
    Node *node = [[Node alloc] initWithData:value];
    [self insertNode:node];
}

Now think about how you do the inserting. Well, if you are an empty tree, your root_ is nil and you can just set it to the new node. Otherwise, you can just ask your root node to insert the new node under himself. Translate that description directly into code:

- (void)insertNode:(Node *)node {
    if (root_ == nil) {
        root_ = node;
    } else {
        [root_ insertNode:node];
    }
}

Now pretend you're a Node. You've been asked to insert a new Node under yourself. How do you do it? You have to compare the new node's value to your value. If the new node's value is less than your value, you want to insert the new node on your left side. Otherwise, you want to insert it on your right side. Translate that description directly into code:

@implementation Node

- (void)insertNode:(Node *)node {
    if (node.data < self.data) {
        [self insertNodeOnLeftSide:node];
    } else {
        [self insertNodeOnRightSide:node];
    }
}

Now you're still a Node, and you've been asked to insert a new node on your left side. How do you do it? Well, if you don't have a child on your left side yet, just use the new node as your left child. Otherwise, you ask your left child to insert the new node under himself. Translate that description directly into code:

- (void)insertNodeOnLeftSide:(Node *)node {
    if (self.left == nil) {
        self.left = node;
    } else {
        [self.left insertNode:node];
    }
}

I'll leave the implementation of insertNodeOnRightSide: as an exercise for the reader. ;^)