What are pointers and why should I learn about them? -- Part 1

Recently, my elder daughter had a programming assignment dealing with binary trees. Her class(sic) is based on Java, which does not seem to have the notion of function pointers. Whether it has other pointers seems to be a matter of definitions, but our inability to imagine an "elegant" solution in Java (which I can barely spell) was irksome to me. Hence, while on an airplane, I coded a more elegant (to my eyes) solution in C, and wondered whether it was possible in Python.

I decided it was, and coded it -- but in spite of its elegance, it required a bit of syntactic anti-sugar. In other words, it was semantically pretty but syntactically ugly. I therefore wrote to a Python mailing-list at the office to ask whether there was a less ugly way to do this.

Unfortunately, the problem was misunderstood, and searches for "pointers python" yielded essentially two things: First, several commented that Python doesn't need pointers, if you're trying to use pointers in Python you're not writing Pythonic stuff, you sould write Python (not C) in Python, etc. Second, recent Pythons apparently have a pointer (or pointers?) class that's associated with calling C APIs from Python. It's an acquaintance of c_long, et al.

It is to this first group of commentators, and anyone who agrees with them, that I address the rest of this posting.

The programming assignment was to balance a binary tree. Basically, starting at the root, we do this:

while (nodes_on_left > nodes_on_right+1) {
    find rightmost node in left subtree: make it the new root
    move old root to be leftmost node in the right subtree
}
while (nodes_on_right > nodes_on_left+1) {
    find leftmost node in right subtree: make it the new root
    move old root to be rightmost node in the left subtree
}
balance left subtree
balance right subtree 

She wrote basically the above in Java, and all the while I was wondering, can't we code it as

#define MOVE_ONE(FROMSIDE,TOSIDE) 
   find TOSIDE##most node in FROMSIDE subtree: make it new root 
   move old root to be FROMSIDE##most node in TOSIDE subtree 

and then the recursive subroutine can be

while (nodes_on_left > nodes_on_right+1) {
    MOVE_ONE(left,right)
}
while (nodes_on_right > nodes_on_left+1) {
    MOVE_ONE(right,left)
}
balance left subtree
balance right subtree 

or something like this? Apparently not in Java.

I was wrong (what, again??) -- see part 2 where I discover that I've been looking at this all wrong.

Bah, I must work on taxes now; to be continued...