Binary Tree in Objective-C

binary-search-tree, binary-tree, ios, objective-c

Solution

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.

Problem

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!

Original source