Invalid Node Height
I am responding in this thread because my problem seems to be similar but I found a solution that does not appear to be posted on this site.
The story:
I am using a 20", Intel, iMac, running the 10.4.11 OS.
I was having problems with a Lacie external drive (1 TB with firewire). When trying to solve the problem I used Disk Utility to Verify the external drive. I then thought, "Well, let me check my HD drive while I am here." When I attempted to Verify my Mac HD drive I got an error similar to those described here except it said, "Invalid Node Height" instead of "Invalid Node Structure." Disk Utility did not offer me an option to "Repair;" the button was simply not active. I read all the things here about partitioning, etc. but was not convinced I needed to go that far. My computer would boot without problems and other than an annoying screen flicker, which has been a constant issue with this computer, everything seemed to be working. Still, I reasoned, as others in this thread have, that I needed to fix the problem before something bad happened.
Here is what I did to Repair the Mac HD:
I shut down the computer and unplugged everything except the mouse and keyboard and turned the comp back on.
I then restarted my comp using Disk 1 of my MAC OS Installation disk as my start up disk instead of my Mac HD. I held down "D" during restart which I thought would open an Apple Hardware Test. My idea was to check the drive for a hardware problem. Instead of hardware test prompts, I was asked to select my language, I released the "D" key, selected English as my language, and got a screen with an activity bar saying "Preparing Installation" or something. Then, I was offered a window asking me if I wanted to proceed with the Installation of software apps that came with my computer. Ignoring this window, I went to top of my screen and found the Disk Utility located on the start up disk. I used it to check the Mac HD and got the same old Invalid Node Height error, but this time I was offered an opportunity to repair, i.e. the button was active. I chose Repair, waited perhaps 20 mins for the repair to complete, verified the Mac HD just to be sure, and then restarted the comp using the Mac HD drive as the Startup Disk.
Everything seems to be fine, no data loss as far as I can tell. I have the same image for my desktop etc.
Hope this helps someone. Peace.